上下文无关文法的基本概念.docVIP

上下文无关文法的基本概念 定义 ：上下文无关文法G是一个四元组G = (N，T，P，S)，其中 N是非终结符的有限集合； T是终结符或单词的有限集合，它与N不相交； P是形如A →α的产生式的有限集合，其中A∈N,α∈V﹡,V=T∪N S是N中的区分符号，称为开始符号或句子符号。V中的符号称为文法符号，包括终结符和非终结符。 特殊情况：A →ε空产生式 例如， if语句结构的文法产生式表示： stmt → if expr then stmt else stmt Backus - Naur范式（Backus-Naur form）或BNF文法 符号的使用约定 ： 符号是终结符： 字母表中比较靠前的小写字母，如a，b，c等。 操作符，如 +、-等。 标点符号，如括号、逗号等。 数字0，1，…，9。 黑体串，如 id、if等。 符号的使用约定 ： 下列符号是非终结符： 字母表中比较靠前的大写字母，如A、B、C等。 字母S，它常常代表开始符号。 小写斜体名字，如expr、stmt等。 字母表中比较靠后的大写字母，如X、Y、Z等，表示文法符号，也就是说，可以是非终结符也可以是终结符。 符号的使用约定 ： 字母表中比较靠后的小写字母，如 u，v，…，z等，表示终结符号的串。 小写希腊字母，如α、β、γ等，表示文法符号的串。因此，一个通用产生式可以写作A → α，箭头左边（产生式左部）是一个非终结符A，箭头右边是文法符号串（产生式右部）。 符号的使用约定 ： 如果A → α1、A → α2、…、A → αk 是所有以A为左部的产生式（称为A产生式），则可以把它们写成A → α1|α2|…|αk，我们将α1、α2、…、αk称为A的候选式。除非另有说明，否则第一个产生式左部的符号是开始符号。 例1 考虑下面的关于简单算术表达式的文法，非终结符为表达式和运算符，终结符有ID,+,-,*,/,(,(,)。产生式有 表达式 ( 表达式 运算符 表达式 表达式 ( (表达式) 表达式 ( - 表达式 表达式 ( ID 运算符 ( + 运算符 ( - 运算符 ( * 运算符 ( / 运算符 ( ( 正规表达式和上下文无关文法的关系： 正规表达式所描述的每一种语言结构都可以用上下文无关文法来描述。 NFA转换成一个等价CFG(上下文无关文法) 对NFA的每个状态i，创建一个非终结符Ai。 如果在状态i输入符号a转换到状态j,则引入产生式 Ai → a Aj 。 如果在状态i输入符号ε转换到状态j, 则引入产生式 Ai → Aj。 如果状态i是接受状态，则引入产生式Ai →ε。 如果状态i是开始状态，则Ai 是文法的开始符号。 分析和推导 文法是用来定义一个语言的，那么，它是如何定义的？ 分析树的建立过程 推导，其核心思想是把产生式看成重写规则，即用产生式右部的串来代替左部的非终结符，实际上也可以看成是从上而下推导分析树的精确描述 表达式(52-6) * 32的推导过程： E ( E op E [E → E op E] ( ( E )op E [E → (E )] ( ( E ) op number [E → number] ( ( E ) * number [op →*] ( (E op E) * number [E → E op E] ( (E op number) * number [E → number] ( (E – number) * number [op → -] ( (number – number) * number [E → number] 如果(1 ( (2 ( (3 ( (4 ( (5 ( (6…( (n ,则说(1推导出(n。一般，符号(表示“一步推导”，通常我们用(*表示“零步或多步推导”，用(+表示“一步或多步推导” 由推导从E 符号中得到的所有记号符号的串集是被表达式的文法定义的语言。这个语言包括了所有合乎语法的表达式。由上下文无关文法产生的语言称为上下文无关语言，如果两个文法产生同样的语言，则称这两个文法等价。 可将它用符号表示为： L (G) = {s | E ( * s } 其中G代表表达式文法，s 代表记号符号的任意数组串。 文法生成的语言示例： 例 考虑带有单个文法规则的文法G E → (E )|a 例 考虑带有单个文法规则文法G