上下文无关文法与语言.pptVIP

上下文无关文法与语言 2005.3 引 言 从语法角度对程序设计语言的代码进行处理。对于程序设计语言的语法描述，将使用上下文无关文法的表示法，这种表示法又称为巴科斯范式，即BNF描述。这种表示法作为语言的语法描述有明显的优点：对程序可给出精确易懂的语法描述；从描述语言的文法可以自动构造出可用的分析程序；在语言的语法描述中，可以方便地插入相关的语义描述，进行语法制导的语义翻译。 主要内容 上下文无关文法的基本概念 分析和推导 文法的设计 乔姆斯基层次及上下文无关文法的局限 上下文无关文法的基本概念 定义 ：上下文无关文法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 – num