字母表和字符串
- 字母表:符号的非空有限集,例如
- 符号:字母表中的元素,例如
- 符号串:符号的有穷序列,例如
- 空符号串:没有任何符号的符号串,例如
约定
用a,b,c,d...,r和S,T,U,V,W,X,Y,Z来表示符号
用s,t,u,v,w,x,y,z来表示符号串
用A,B,C,D,...,R来表示符号串集合
文法
文法是在形式上对句子结构的定义和描述,未涉及到语义问题
语法树/语法推导树
- 语法成分:又叫非终结符
- 单词符号:又叫终结符号
文法的定义
定义文法
规则:规则是一个有序对
推导
定义文法
语言
假设我们有文法
- 句型:
是句型 且 - 句子:
是句子 且 - 语言:
,即由文法 所产生的句子的集合
句型的定义更宽松一点,句子也满足句型的定义
等价文法:设
短语:若
,且 ,则 是句型 相对于 的短语,由每棵子树的叶子组成 简单短语:若
,且 ,则 是句型 相对于 的简单短语,设简单子树为高度为两层的子树,每棵简单子树的叶子组成的就是简单短语
直观理解:短语是前面句型中某个非终结符所能推导出的符号串
- 句柄:任一句型的最左简单短语称为该句型的句柄,由最左边的简单子树的叶子组成
二义性
若对于一个文法的某一个句型,存在两棵不同的语法树,则该文法是二义性文法,否则是无二义性文法
文法的二义性是不可判定的
若文法存在二义性,那么编译的时候就会产生不确定性,现在的解决方法是,提出一些限制条件,称为无二义性的充分条件,当文法满足这些条件时,就可以判定文法是无二义性的
也可以不改变二义性文法,而在代码实现层面上,保证不会出现编译错误