编译原理2-文法与语言

字母表和字符串

• 字母表：符号的非空有限集，例如
• 符号：字母表中的元素，例如
• 符号串：符号的有穷序列，例如
• 空符号串：没有任何符号的符号串，例如

约定

用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来表示符号串集合

文法

文法是在形式上对句子结构的定义和描述，未涉及到语义问题

语法树/语法推导树

• 语法成分：又叫非终结符
• 单词符号：又叫终结符号

文法的定义

定义文法，其中：

：非终结符号集

：终结符号集

：产生式或规则的集合

：开始符号/识别符号，

，称为文法的字汇表

规则：规则是一个有序对，通常写为或，其中

推导

定义文法 相当于在语法树上拓展了某一个节点，例如：

则表示在语法树上经过了次拓展 则表示在语法树上经过了次拓展

语言

假设我们有文法

• 句型：是句型 且
• 句子：是句子 且
• 语言：，即由文法所产生的句子的集合

句型的定义更宽松一点，句子也满足句型的定义

等价文法：设和是两个不同的文法，若，则和为等价文法

• 短语：若，且，则是句型相对于的短语，由每棵子树的叶子组成

• 简单短语：若，且，则是句型相对于的简单短语，设简单子树为高度为两层的子树，每棵简单子树的叶子组成的就是简单短语

直观理解：短语是前面句型中某个非终结符所能推导出的符号串

• 句柄：任一句型的最左简单短语称为该句型的句柄，由最左边的简单子树的叶子组成

二义性

若对于一个文法的某一个句型，存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法

文法的二义性是不可判定的

若文法存在二义性，那么编译的时候就会产生不确定性，现在的解决方法是，提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的

也可以不改变二义性文法，而在代码实现层面上，保证不会出现编译错误