文法和语言

14 Oct, 2021

编译原理-文法和语言

元素非空的又穷集合，包含了语言中允许出现的全部符号

有字母表Σ中的符号所组成的任何有穷序列。无任何符号的符号产称为空符号串，记作ε

符号串中符号的个数。字符串"110011"的长度 = |110011| = 6 ,空串ε的长度为0

设w是一个符号串，把从w的尾部删除0个或若干个符号后剩余之后的部分称为w的前缀。同理后缀

从一个符号串总删去他的一个前缀和一个后缀之后剩余的部分称为该符号串的字符号串或字串

设w是某字母表上的符号串，把w自身连接n次得到的符号串即v = www...ww(n个w)，称v是w的n次幂

w^0 = ε

设A是一个集合，A的正闭包记作A^+ 定义为:

A^+ = A^1 ∪ A^2 ∪…∪ A^n∪…

A^* 定义为A的自反闭包，显然有:

A^* = A^0 ∪A^1 ∪ A^2 ∪…∪ A^n∪…

一部文法G是一个四元组

G = (V_N,V_T,S,P)

V_N:非空有限的非终结符集合

V_T:非空有限的终结符集合

S:文法的开始符号,S属于V_N

P:产生式集合。产生式是按一定格式书写的定义原发范畴的文法规则

A、B、C等大写字母表示非终结符

a,b,c等小写字母表示终结符

α，β，γ等希腊字母表示文法符号串。文法符号串是由终结符和非终结符组成的符号串

文法G=(V_N,V_T,S,P)。ζ，γ∈(V_N∪V_T)^* ,若S=*>ζαγ，且存在a->β，则称ζαγ直接推导出ζβγ，记作ζαγ=>ζβγ，与之相应，称ζβγ直接规约到ζαγ。

设有文法G=(V_N,V_T,S,P)，若存在ω = α0=>α1=>…αn-1=>αn = υ

如果 S⇒* α，α∈(VT∪VN)*，则称α是G的一个句型 (sentential form)。

一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串。

如果 S⇒* w，w ∈VT*，则称w是G的一个句子(sentence)。

句子是不包含非终结符的句型。

在每一步推导过程中，总是对字符串中最左(右)边的非终结符进行替换

语法分析树来表示经推导而产生的句子结构，有助于理解句子的语法结构层次。

根由开始符号所标记；
每个叶子由一个终结符、非终结符或 ε 标记；
每个内部节点都是非终结符；
若 A 是某节点的内部标记，且 X1、X2…Xn 是该节点从左到右的所有孩子的标记。则：A→X1X2…Xn 是一个产生式。若 A→ε，则标记为 A 的节点可以仅有一个标记为 ε 的孩子。若 A→ε ，则标记为 A 的节点可以仅有一个标记为 ε 的孩子。

一个句子可能对应多于一棵语法树。

这种问题由"句子产生过程中的某些推导有多于一种选择"引起。