编译原理 第2章 文法和语言的基本知识.ppt

程序设计语言是一种形式语言，与自然语言既有相似的性质又有本质的不同。 最主要的区别是：形式语言的规则简单、严格、无例外、无二义性。 编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上。 语法——文法是描述语言语法的形式规则 语义——语言中各语句的含义 语用——从使用者的角度对语言的描述 文法的直观概念：以汉语中的“我是大学生”为例。 文法的形式定义：P10的定义1.1 例2-1，文法G=（ ， ，P，S）是描述标识符的文法，则其中： ={标识符，字母，数字} ={a,b,c….x,y,z,0,1,2,3…9} P ={标识符 字母|标识符字母| 标识符数字 字母 a|b|c|….|z 数字 0|1|2|….|9} S =标识符 例2-3，利用例2-2中的文法，推导出文法的句子012： 最左推导：N =S =SD =SDD =DDD =0DD =01D =012 最右推导：N =S =SD =S2 =SD2 =S12 =D12 =012 在这里，N S为长度为1的推导， N SD为长度为2的推导 N 012为长度为7的推导。其中，对于N S来说，S是N的直接推 导，或N是S的直接归约。 一些规定： =推导 =规范推导 长度大于零的推导 长度可为零的推导 长度为n的推导 课堂作业： 设有文法G[S]： S→a|ε|（T） T →T，S|S 请给出句子（a,(a,a))的最左、最右推导。 短语与句柄 P18 定义：设G[S]是一个文法，并设w=xuy 是该文法的一个句型。若S?*xUy且U?+u，则称u为句型w=xuy对非终结符U的一个短语。若S?*xUy且U?u，则称u为句型w=xuy相对于非终结符U的一个简单(直接）短语。任何一个句型的最左简单短语称为柄短语（句柄）。 含有终结符的短语，并且不存在也具有这种性质真子串的短语称为素短语。P72 例：表达式文法G[E] ： E→E+T|T T→T*F|F F→(E)|i 对句型i*(E)的推导为： E?T ?T*F ? F*F ?i*F ? i*(E) 对应的推导树为： 语法树与短语 使用推导树计算句型（句子）的短语简单、明了 推导S ?*xUy U ?+u 等价于： 等价于： S U xUy u 因此称u是句型xuy(对U)的一个短语 等价于： S xUy u 若子树高度为1，则u还是直接 短语，最左直接短语为句柄。若u是含有终结符的最小的短语，则为素短语，句型最左边的素短语称为最左素短语（P72）。 例：上例的文法G[E] 和句型i*(E)容易从推导树中看出： 短语：i, i*(E), (E) 直接短语：i，(E) 句柄（左直接短语）：i 素短语：i，(E) 最左素短语：i 例，找出针对左边文法的句型T+T*F+a的所有短语、简单短语(直接短语)、素短语和句柄。此句型对应的分析树为： 课堂练习 设有文法G[E]如下： E→E+T|E-T|T T→T*F|T/F|F F→（E）|id 请给出句型（F+id)-T*(E-T)的 所有短语、简单短语和句柄。 S→aSBE S→aBE BE→bE aB→ab bB→bb bE→be eE→ee 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1 　　　　　　 S→ε G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 3型文法(正则文法) G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 标识符（字母开始的字母数字串）的有效长度是10 数字最多为14位 过程无参，可嵌套（最多三层）定义，可递归调用 变量的作用域同PASCAL 13个保留字：if, then, while, do, read, write, call, begin, end, const, var, procedure, odd 以 为子树