第4章语法分析(1)

《第4章语法分析(1)》由会员分享，可在线阅读，更多相关《第4章语法分析(1)（56页珍藏版）》请在金锄头文库上搜索。

1、1,第四章 语法分析,2,本章内容,上下文无关文法 自顶向下分析和自底向上分析 LL文法和LR文法 Yacc,3,4.1 语法分析器的作用,4,4.2 上下文无关文法,正则表达式的局限性 正规式用于定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复。 例：a5b5,a(ba)5, a(ba)* , a* b* 当自动机构造好后，anbn的n是确定的。 正规式不能用于描述配对或嵌套的结构，例： 配对括号串的集合，例如：()() anbn,5,例如，包含递归结构的条件语句不能用正规表达式说明，可以用产生式表示： stmt if expr then stmt else stmt

2、| stmt if then else stmt| 正规表达式：(if then else)*,6,4.2.1上下文无关文法的定义,上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合 VN : 非终结符集合 S : 开始符号， S VN 唯一一个开始符号 P :产生式集合，产生式形式为：A ，AVN, (VNVT )*,stmt if expr then stmt else stmt,statement 语句,7,例4.2 定义算术表达式的文法,expr expr op expr expr (expr) expr expr expr id op + | - | * |

3、 /,operator运算符 operand 操作数,非终结符集合VN =expr,op 终结符集合VT=+,-,*,/, (, ),id expr是开始符号,8,4.2.2 符号的使用约定,我们一般用大写字母表示非终结符，小写字母表示终结符， 终结符Terminals: a, b, c, +, -, punc, 0, 1, 9, Black strings: id, if 非终结符Non-Terminals: A, B, C, S, 斜体串italic strings 文法符号： X, Y, Z 表示非终结符或终结符号 终结符号串： u, v, z in VT* 字母表中排在后面的小写字母

4、文法符号串： , in (VT VN)*,省得对每个文法要说明哪些是终结符，哪些是非终结符。,u=aabbcc =abAcBd,9,符号的使用约定,产生式: A 1; A 2; ; A k; A 1 | 2 | | k,10,E E A E | ( E ) | -E | id A + | - | * | /,例4.2的文法改写为：,expr expr op expr expr (expr) expr expr expr id op + | - | * | /,expr expr op expr | ( expr ) | -expr| id op + | - | * | /,或,11,4.2.3

5、 推导,把产生式看成重写规则，用产生式右部的串来代替左部的非终结符。 例: E E + E | E * E | (E ) | E | id E E (E) (E + E) (id + E) (id + id) (id + id)是文法的句子。 (id + E)等是文法的句型。,stop him watching TV stop doing .,12,推导的定义,定义：设有文法G = ( VT, VN, S, P)，称串A直接推导出，如果A P，且, (VTVN)*，并记作A 。 称 直接归约到A。 如果存在一个直接推导序列： 0 1 . n (n=0), 则称0推导出n，记作0n（推导长度为n

6、）。,E E (E) (E + E) (id + E) (id + id),13,推导,表示一步推导(直接推导) 表示零步或多步推导 对任意串 如果 表示一步或多步推导,+, ,*,14,句型、句子、语言,对开始符号为S的文法G，wL(G)，当且仅当 称w为G的句子。 对开始符号为S的文法G，如果 ，则称为G的句型。 句子是不含非终结符的句型。 仅含终结符号的句型是一个句子。 语言L(G)是由文法G产生的所有句子的集合： 若文法G1和文法G2所产生的语言相同，即L(G1) = L(G2)，则称文法G1和文法G2等价。,一个C语言程序就是C语言的一个句子。,E E (E) (E + E) (id

7、 + E) (id + id),15,S aSb aaSbb a3Sb3 an-1Sbn-1 anbn 显然，L(G) = anbn n1 。,例：已知文法G = ( a, b, S, S, P )， 其中 P：S aSb ab,16,最左推导left most,最左推导：推导过程中任何一步推导都是对中的最左非终结符进行替换。 如果是最左推导，可以记为 如果 ，则称是文法的左句型。,17,最右推导,类似的，可以定义最右推导：推导过程中任何一步推导 都是对中的最右非终结符进行替换。 最右推导也称作规范推导。,18,归约（reduce）,定义：设和均为句型，若，则称可以归约为。 规范（最右）推导的

8、逆过程，称为规范归约。 语法分析的核心问题就是，对于一个终结符号串x，设法从S推导出x，或者反过来，设法将x归约为S。,*,最右推导的逆反就是最左归约,19,4.2.4 分析树和推导,分析树是推导的图形表示。,-(id+id)的分析树,20,例4.5 从最左推导构造的分析树,21,例4.5 从最右推导构造的分析树,22,设串是文法G的句型，则至少存在一棵分析树，它的叶子从左至右排列恰好就是。 注意，分析树的形状与推导顺序无关，而与在推导时，所选择的对句型中的非终结符号进行替换的产生式有关。 每棵分析树都有与之对应的唯一的最左推导和最右推导。 但是，每个句子不一定只有唯一的分析树。,句型与分析树

9、的关系,-(id+id),id * id + id,23,4.2.5 二义性,二义性的一些例子 I saw a man in the hill with a telescope. 球拍卖完了。 父在子先亡。,24,四个人在打麻将，周围没有旁观者，但是派出所却带走了5个人（不包括警察）。请问这是为什么？,25,文法句子id * id + id有两个不同的最左推导：,E E * E E E + E id * E E * E +E id * E + E id * E + E id * id + E id * id + E id * id + id id * id + id,26,二义性用分析树表示比

10、较直观,E E * E E E + E id * E E * E +E id * E + E id * E + E id * id + E id * id + E id * id + id id * id + id,27,文法的二义性,如果一个文法的句子存在两棵分析树，那么，该句子是二义性的。 如果一个文法包含二义性的句子，则说这个文法是二义性文法；否则说该文法是无二义性文法。 文法的二义性源于这样的事实：在一个句型中，存在一个非终结符号A，对于它有两条产生式可用于替换，但A的这些推导最终都产生相同的句型。,28,文法的二义性,二义性是文法的性质。程序设计语言是无二义的。（自然语言本质是二义的

11、，在一定语境下没有二义） 文法的二义性的消除：改写文法,E E + E | E * E | (E ) | id,改写成,E E + T | T （ T + T . . . + T ） T T * F | F （ F * F . . . * F ） F ( E ) | id,29,4.2.6 验证文法产生的语言,例4.7 G : S (S) S | L(G) = 配对的括号串的集合 要证明两个问题：（1）推出的是配对括号串 （2）所有的配对括号串可由S推出 按推导步数进行归纳：推出的是配对括号串 归纳基础： S 归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下： S (S

12、 )S (x) S (x) y,+,+,30,按串长进行归纳：所有的配对括号串w可由S推出 归纳基础： S 归纳假设：长度小于2n的都可以从S推导出来 归纳步骤：考虑长度为2n(n 1)的w = (x) y 即令(x)：是w中的最短的、左括号个数和右括号个数相同的非空前缀 S (S )S (x) S (x) y,() () () ()()(),y,(x),*,*,31,4.2.7 正规式和上下文无关文法,正规语言(RL)是上下文无关语言(CFL)的真子集，正规表达式所描述的语言可以用上下文无关文法描述。 将正规式转换为NFA，再将NFA转换为等价的CFG。,RL: Regular Langua

13、ge CFL: Context Free Language CFG: Context Free Grammar,32,将正规表达式(a|b)*ab用CFG表示,正规式 (a|b)*ab 文法 A0 a A0 | b A0 | a A1 A1 b A2 A2 ,aabbab,33,a,构造规则,每个状态 i 有一个对应的非终结符 Ai If then Ai a Aj If then Ai Aj 如果 i 是终结状态, Ai 如果 i 是起始状态, Ai 是开始符号,这些规则也可以把正规文法转换为NFA。,34,正规文法,若文法G = (VT, VN, S, P)中的每一个产生式形如： A aB

14、或 A a 其中A, BVN, aVT ，则称G为右线性文法。 若文法G=(VT, VN, S, P)中的每一个产生式形如： A Ba 或 A a 则称G为左线性文法。 右线性文法和左线性文法都称为3型文法(正规文法)。,35,形式语言鸟瞰,Chomsky在1956创立了形式语言学，并将形式语言的文法分为四类：文法 G = (VT, VN, S, P) 0型文法(短语结构文法, PSG) ， , (VN VT)*, | 1 1型文法(上下文有关文法, CSG) | |，但S 可以例外 2型文法(上下文无关文法, CFG) A ，AVN , (VN VT)* 3型文法(正规文法, RG) A aB或A a，A, BVN , a VT,36,4.3.5 非上下文无关的语言结构,L1 = wcw | w属于(a | b)* “检查标识符的声明应先于其引用”的抽象 L2 = anbmcndm | n 0, m 0 “检查形参个数和实参个数应该相同”的抽象 L3 = anbncn | n 0 “打字机打印下划线字符”的抽象,37,注意：一些类似的语言却是CFG。,L1= wcwR | w(a|b)* S aSa | bSb | c L2 = anbmcmdn | n 1, m 1