打印词法分析和语法分析.ppt

1、2020/8/4,北京化工大学信息科学与技术学院计算机系,1,Chapter 3 Scanning(lexical analysis)词法分析,3.1 词法分析器的作用 3.2 记号的描述 3.3 记号的识别 3.4 从正规表达式到DFA 3.5 TINY扫描程序的实现 3.6 LEX,2020/8/4,北京化工大学信息科学与技术学院计算机系,2,3.1 词法分析器的作用,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成, The phase of a compiler 编译程序的结构,目 标 代 码 生 成,2020/

2、8/4,北京化工大学信息科学与技术学院计算机系,3,3.1 词法分析器的作用,读入输入字符，产生记号序列，供语法分析使用 3.1.1 词法分析中的问题 3.1.2 记号 3.1.3 记号的属性,2020/8/4,北京化工大学信息科学与技术学院计算机系,4,3.1 词法分析器的作用,3.1.1 词法分析中的问题,把编译过程的分析阶段划分为词法分析和语法分析的原因如下： 1. 简化编译器的设计可能是最重要的考虑。 2. 提高编译器的效率。 3. 增强编译器的可移植性。,2020/8/4,北京化工大学信息科学与技术学院计算机系,5,3.1 词法分析器的作用,3.1.2 记号: 扫描程序生成的逻辑单元

3、,以字母开头： 保留字：IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE 标识符：字母/数字串 以数字开头： 整常数：数字开头的数字串 实常数：整数.整数 符号词：+，-，*，/，(，)，:，:=，;，. 控制词：enter,Reserved Words 保留字,2020/8/4,北京化工大学信息科学与技术学院计算机系,6,typedef enum /* book-keeping tokens */ ENDFILE,ERROR, /* reserved words */ IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE, /* m

4、ulticharacter tokens */ ID,NUM, /* special symbols */ ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI TokenType;, Tokens(记号)的枚举表示,每一个记号的表示： Typedef struct TokenType tokenval; char *stringval; int numval; TokenRecord,2020/8/4,北京化工大学信息科学与技术学院计算机系,7,3.1.3记号的属性 任何与记号相关的值 E = M * C ,3.1 词法分析器的作用,20

5、20/8/4,北京化工大学信息科学与技术学院计算机系,8,3.2 记号的描述,be set of the ASCII characters or some subset of it,3.2.1 串和语言 3.2.2 语言上的运算,2020/8/4,北京化工大学信息科学与技术学院计算机系,9, The single character from the alphabet, expression a matches the character a. L(a) = a empty string(): the string contains no characters. L() = or : matc

6、hes no string at all ,whose language is the empty set. L() = ,3.2.3 Definition of Regular Expression,1. Basic Regular Expression 基本正则表达式,2020/8/4,北京化工大学信息科学与技术学院计算机系,10, | Choice among alternatives 或(选择),2. Regular Expression Operation 正则表达式的运算,L(r|s) = L(r ) L(s ) L(a|b|c|d) = a,b,c,d,例：若S= a|bb， (

7、a|bb)* =？L(a|bb)*)=？,(a|bb)* =,a,bb,aa,abb,bba,bbbb,aaa,aabb, L(a|bb)*)=L(a|bb)*=a|bb*=,a,bb,aa,abb,bba,bbbb,aaa,aabb,abba,abbbb,bbaa,2020/8/4,北京化工大学信息科学与技术学院计算机系,11, Names for regular expression 正则表达式的名字, Precedence of Operation and use of parentheses 运算符的优先级和括号的使用,Precedence of Operation运算符的优先级,Pr

8、ecedence: * the first the second |the third,(0|1|2|3|9)(0|1|2|3|9)*,例：a|bc* a|(b(c*) ab|c*d (ab)|(c*)d),(先*，其次 ，最后 |),digit = 0|1|2|3|4|9 digit digit*,2020/8/4,北京化工大学信息科学与技术学院计算机系,12,3. Example,1)= a,b,c the set of all strings over this alphabet that contain exactly one b. (上只包括一个b的所有串的集合),(a|c)*b(a

9、|c)*,2) = a,b,c the set of all strings that contain at most one b. (上最多包括一个b的所有串的集合),(a|c)*|(a|c)*b(a|c)* (a|c)*(b|)(a|c)*,3) = a,b the set of strings S consists of a single b surrounded by the same number of as.(上由一个b及在其前后有相同数目的a组成的串S的集合),S = b,aba,aabaa,aaabaaa,“regular expression cant count ”,202

10、0/8/4,北京化工大学信息科学与技术学院计算机系,13,3. Example,4) = a,b,cthe strings contain no two consecutive bs (上任意两个b都不相连的所有串的集合),( not b | b not b )* ( b |) not b = a|c (a | c | ba | bc)* (b |) (b |) (a | c | ab| cb )*,5) = a,b,c, Regular Expression :(b|c)* a(b|c)*a)* (b|c)*, determine a concise English description

11、of the language (正则表达式描述语言),the strings contain an even number of as 偶数个a的串的语言,(b|c)* a(b|c)*a)* (b|c)* ( not a* a not a* a)* not a*,2020/8/4,北京化工大学信息科学与技术学院计算机系,14,3.2.4 Extensions to Regular Expressions,r? the strings matched by r are optional,1. one or more repetitions 一个或多个重复(正闭包),r+,2. any char

12、acter 任意字符,period “”,3. a range of characters 字符范围,0-9, a-zA-Z,4. any character not in a given set 不在给定集合中的任意字符,(a|b|c) a character that is not either a or b or c abc in Lex,5. optional subexpressions 可选的表达式,2020/8/4,北京化工大学信息科学与技术学院计算机系,15,Regular Expressions for Programming Language Tokens,1. Numbe

13、rs 数,nat = 0-9+ signedNat = (+|-)?nat number = signedNat(“”nat)? (E signedNat)?,2. Reserved Words and Identifiers 保留字和标识符,reserved = if | while | do | letter = a-z A-Z digit = 0-9 identifier = letter(letter|digit)*,3. Comments 注释,/* this is a C comment */ this is a pascal comment ,4.Ambiguity, White

14、 Space, and Lookahead 二义性、空格、回溯,2020/8/4,北京化工大学信息科学与技术学院计算机系,16,3.2.5 正则文法,2020/8/4,北京化工大学信息科学与技术学院计算机系,17,3.3 记号的识别,状态转换图 有穷自动机,2020/8/4,北京化工大学信息科学与技术学院计算机系,18,3.3.1 状态转换图,状态转换图的表示方法,结点代表状态(state)，用圆圈表示。 状态之间用箭弧(transition)连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。 一个有穷自动机只包含有限个状态(即有限个结点)，其中一个为初

15、态(start state)，至少一个为终态(接受状态accepting state) (双圈表示)。,2020/8/4,北京化工大学信息科学与技术学院计算机系,19,3.3.2 Finite Automata有穷自动机,Finite automata( finite-state machines) are a mathematical way of describing particular kinds of algorithms.,Definite of Deterministic finite automation(DFA) 确定有穷自动机 Nondeterministic finite

16、 automation(NFA) 非确定有穷自动机,2020/8/4,北京化工大学信息科学与技术学院计算机系,20, Definite of Deterministic finite automation(DFA) 确定有穷自动机,由M接受的语言L(M) L(M) | ci , s1= T(s0,c1), s2= T(s1,c2), , sn = T(sn-1,cn) , sn A. , DFA(deterministic finite automation)M ：,“确定” 即状态转移函数是单值函数, an alphabet 输入字母表（终极符集合） a set of stat

17、es S 有穷状态集（非终极符集合） a transition function T : S S (状态转换函数) a start state s0S 唯一的初始状态 a set of accepting states A S 终止状态集,2020/8/4,北京化工大学信息科学与技术学院计算机系,21, Example,1) exactly one b. (上只包括一个b的所有串的集合),2) most one b. (上最多包括一个b的所有串的集合),(not b)*b(not b)*,(not b)*(b| )(not b)*,2020/8/4,北京化工大学信息科学与技术学院计算机系,22

18、, Example,3) digit = 0-9 nat = digit + signedNat = (+|-)? Nat Number = singedNat(“.”nat)?(E signedNat)?,2020/8/4,北京化工大学信息科学与技术学院计算机系,23,例：有DFA M=(0,1,2,3,a,b, T,0,3) 其中T为:T(0,a)=1 T(0,b)=2 T(1,a)=3 T(1,b)=2 T(2,a)=1 T(2,b)=3 T(3,a)=3 T(3,b)=3,它所对应的状态表如图：,一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示T(s,a)的

19、值，这个矩阵称状态表（状态转移矩阵）。,状态,输入字符,后继 状态, 状态表,2020/8/4,北京化工大学信息科学与技术学院计算机系,24, Nondeterministic finite automation(NFA) 非确定有穷自动机,由M接受的语言L(M) L(M) | ciU, s1= T(s0,c1), s2= T(s1,c2), , sn = T(sn-1,cn) , sn A. , NFA M ：,“非确定” 即状态转移函数是多值函数, an alphabet 输入字母表（终极符集合） a set of states S 有穷状态集（非终极符集合） a trans

20、ition function T: S x ( U)(S)(状态转换函数) a set of start states S0 S 初始状态集 a set of accepting states A S 终止状态集,2020/8/4,北京化工大学信息科学与技术学院计算机系,25,2020/8/4,北京化工大学信息科学与技术学院计算机系,26,DFA,NFA,2020/8/4,北京化工大学信息科学与技术学院计算机系,27, Implementation of finite automata in Code 用代码实现有穷自动机, 识别标识符的DFA （方法1）：, starting

21、in state 1 if the next character is a letter then advance the input; now in state 2 while the next character is a letter or a digit do advance the input; stay in state 2 end while; go to state 3 without advancing the input accept; else error or other cases end if;,2020/8/4,北京化工大学信息科学与技术学院计算机系,28, 识别

22、标识符的DFA （方法2）：,state := 1; ch := next input character; while not Acceptstote and not error(state) do newstate := Tstate,ch; if Advancestate,ch then ch := next input character; state := newstate; end while; if Acceptstate then accept;,2020/8/4,北京化工大学信息科学与技术学院计算机系,29,3.4 From Regular Expression To DFA

23、s从正则表达式到DFA,1. (a)对于正则式,所构造NFA:,x,y,(b)对于正则式,所构造NFA:,x,y,(c)对于正则式a,a,则 NFA:,x,y,a,the algorithm : translating a regular expression into a DFA,3.5.1 从正则表达式到NFA,2020/8/4,北京化工大学信息科学与技术学院计算机系,30,2. 若s,t为上的正则式,相应的NFA分别为N(s)和N(t);,(a)对于正则式R=s|t, NFA(R),(b)对正则式R=st,NFA(R),(c)对于正则式R=s*, NFA(R),(d)对R=(s),与R=

24、S的NFA一样.,例:为R=(a|b)*abb构造NFA,使得L(N)=L(R),分解R的方法有很多种！,R=(a|b)*abb,2020/8/4,北京化工大学信息科学与技术学院计算机系,33, 从正则表达式到NFA 方法二:,AB,i,A,B,i,k,A|B,i,A*,i,A,B,i,i,k,A,NFA替换规则(NFA允许边出现),2020/8/4,北京化工大学信息科学与技术学院计算机系,34,例：令=a,b， 上所有含有两个相继的a或两个相继的b的字的集合用NFA表示如下：,(a|b)* (aa|bb) (a|b)*,NFA M=( 0,1,2,3,4,5,6,7 , a,b , T, 0

25、 , 7 ) 其中T如上（不可省略）,初态,终态,(a|b)* (aa|bb) (a|b)*,2020/8/4,北京化工大学信息科学与技术学院计算机系,35,非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的,NFA M,DFA M,构造成一个,使得 L(M)=L(M),3.4.2 从NFA到DFA,2020/8/4,北京化工大学信息科学与技术学院计算机系,36,（）合并 （如果有S1S2,则把S2状态合并到S1状态） 符号合并,NFA允许边出现, NFA到DFA的区别：, 转换思想：,2020/8/4,北京化工大学信息科学与技术学院计算机系,37,例1：NFA转换成DFA (符号合并)

26、,解：根据题意，得出相应的正则式：0(0|1)*1 得状态转换图(NFA)如下：,2020/8/4,北京化工大学信息科学与技术学院计算机系,38,NFA确定为DFA过程： DFA的初态（为NFA的初始状态经过合并后的状态的并集）例：T(S,)=; DFA的其它状态（ 为NFA的状态经过输入符号后产生的状态，再经过合并后的状态的并集）例：求T(S,0)=？ T(S,0)=A; T(A,)=B; T(B,)=C; T(C,)=； DFA的终态（为所有含有NFA的终态的状态）,0,1,0,C,S,A,B,1,2020/8/4,北京化工大学信息科学与技术学院计算机系,39,NFA确定化过程： (初态、

27、其它状态、终态),0,1,0,C,S,A,B,1,2020/8/4,北京化工大学信息科学与技术学院计算机系,40,得状态转换图(DFA)如下：,在DFA中，所有含有NFA的终态的状态作为DFA的终态,DFA M=( S,A,B,C , 0,1 , T, S , C ) 其中T如上（不可省略）,2020/8/4,北京化工大学信息科学与技术学院计算机系,41,定义1：状态集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为： 1）若sI，则s-closure（I）； 2）若sI，则从s出发经过任意条弧能够到达的任何状态都属于-closure（I）。 状态集-closure（I）称

28、为I的-闭包,为了使得NFA确定化，给出两个定义：,解：根据定义： -closure（I）=1，3,2020/8/4,北京化工大学信息科学与技术学院计算机系,42, J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合。, Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过弧到达的状态。,定义2: 状态子集的构造：,sI,Ia=-closure(J) =-closure(T(1，a)） =-closure(2，4） =2，4，6,令I是NFA M的状态集的一个子集, a 定义: Ia=-closure(J) 其中J = T(s,a),2020/8/4,北京化工大学信

29、息科学与技术学院计算机系,43,例：有NFA M，求DFA M。,初态,I=-closure(1)=1,4,Ia=-closure(T(1,a)T(4,a) = -closure(2,3） = -closure (2,3) =2,3,Ib= -closure(T(1,b)T(4,b) = -closure(） =,Ic= -closure(T(1,c)T(4,c) = ,I=2,3, Ia=2,Ib=4,Ic=3,4 ,1,4,2020/8/4,北京化工大学信息科学与技术学院计算机系,44,DFA M状态表,将求得的状态转换矩阵重新编号,2020/8/4,北京化工大学信息科学与技术学院计算机系

30、,45,“对于任一个DFA，存在一个唯一的状态最少的等价的DFA” 一个有穷自动机是化简的 没有多余状态 并且 状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。,3.4.3 DFA的化简 (极小化),2020/8/4,北京化工大学信息科学与技术学院计算机系,46,有穷自动机的多余状态： 从该自动机的开始状态出发，任何输入串也不能到达那个状态。,2020/8/4,北京化工大学信息科学与技术学院计算机系,47,(2)等价状态 状态s和t的等价条件是:,1) 一致性条件：状态s和t必须同时为可接受状态或不接受状态. 2) 蔓延性条

31、件：对于所有输入符号,状态s和t必须转换到等价的状态里.,对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同 的后继，则称s，t是等价的。 （任何有后继的状态和任何无后继的状态一定不等价）,有穷自动机的状态s和t不等价,称这两个状态是可区别的。,2020/8/4,北京化工大学信息科学与技术学院计算机系,48,“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.,最小化DFA的方法：,2020/8/4,北京化工大学信息科学与技术学院计算机系,49,解:,(一)区分终态与非终态,a,b

32、,2,4,3,1,srart,a,a,a,a,a,a,a,b,b,b,b,b,b,b,2020/8/4,北京化工大学信息科学与技术学院计算机系,50,区号,区号,2020/8/4,北京化工大学信息科学与技术学院计算机系,51,例2：设计一个最小化的DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。化简,DFA M=( S,ABC,BCZ , 0,1 , T,S, BCZ )其中T如上(不可省略),2020/8/4,北京化工大学信息科学与技术学院计算机系,52,例3：试求与下图所示NFA等价的化简了的DFA。,0,0,3,1,1,2,4,0,1,1,0,1,0,1,0,1,化简

33、后的DFA:,2020/8/4,北京化工大学信息科学与技术学院计算机系,53,例4：试构造与正则式R=(a*|b*)b(ba)*等价的状态最少的DFA。,2020/8/4,北京化工大学信息科学与技术学院计算机系,54,NFA确定为DFA:,注：状态从18标注,2020/8/4,北京化工大学信息科学与技术学院计算机系,55,3.5 Implementation of a tiny scanner TINY扫描程序的实现, The tokens and token classes of TINY,Reserved Words Special Symbols Other if + number th

34、en - (1 or more digits) else * end / repeat = until identifier read ( (1 or more letters) write ) ; :=, :Comments,2020/8/4,北京化工大学信息科学与技术学院计算机系,56, The DFA 1 for the special symbols except assignment, The DFA 2 ( numbers and identifiers ),2020/8/4,北京化工大学信息科学与技术学院计算机系,57, The DFA 3 (comments ,white sp

35、ace, assignment ),2020/8/4,北京化工大学信息科学与技术学院计算机系,58, Sample program in the TINY language, sample program In TINY language - Computes factorial read x; input on integer if 0 x then dont compute if x = 0 fact := 1 ; repeat fact := fact * x; x := x - 1 until x = 0; write fact output factorial of x end,20

36、20/8/4,北京化工大学信息科学与技术学院计算机系,59, Output of scanner,TINY COMPILATION: sample.tny 1: Sample program 2: in TINY language 3: computes factorial 4: 5: read x; input an integer 5: reserved word: read 5: id, name= x 5: ; 6: if 0 x then dont compute if x = 0 6: reserved word: if 6: mum, val= 0 6: 6: id, name=

37、 x 6: reserved word: then,7: fact := 1; 7: id, name= fact 7: := 7: num, val= 1 7: |; 8: repeat 8: reserved word: repeat 9: fact := fact * x; 9: id, name= fact 9: := 9: id, name= fact 9: * 9: id, name= x 9: ;,2020/8/4,北京化工大学信息科学与技术学院计算机系,60, Output of scanner,10:x := x - 1 10: id, name= x 10: := 10:

38、id, name=x 10: - 10: mum, val = 1 11:until x = 0; 11: reserved word: until 11: id, name= x 11: = 11: mum, val= 0 11: ; 12: write fact output factorial of x 12: reserved words: write 12: id, name= fact 13:end 13: reserved word: end 14: EOF,2020/8/4,北京化工大学信息科学与技术学院计算机系,61,Chapter 4 Syntax Analysis语法分析

39、,4.1 语法分析器的作用 4.2 上下文无关文法 4.3自顶向下语法分析 4.4自底向上语法分析,2020/8/4,北京化工大学信息科学与技术学院计算机系,62,4.1 语法分析器的作用,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成, The phase of a compiler 编译程序的结构,目 标 代 码 生 成,2020/8/4,北京化工大学信息科学与技术学院计算机系,63,4.1 语法分析器的作用,语法 分析器,词法 分析器,记号流,源程序,前端其他部分,分析树,中间表示,符号表管理器,出错处理器,20

40、20/8/4,北京化工大学信息科学与技术学院计算机系,64,4.1.1 语法错误的处理, 源程序中可能出现的错误 词法错误如非法字符或拼写错关键字、标识符等； 20times: 语法错误是指语法结构出错，如少分号、begin/end不配对等。 beginx:=a+by:=x; 静态语义错误：如类型不一致、参数不匹配等； a,b:integer;x:array1.10 of integer; x:=a+b; 动态语义错误（逻辑错误）：如无穷递归、变量为零时作除数等。 while (t) .;a:=a/b;,2020/8/4,北京化工大学信息科学与技术学院计算机系,65,4.1.1 语法错误的处理

41、, 语法错误处理的目标 清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报； 迅速地从每个错误中恢复过来（以便分析继续进行）； 不应使对语法正确源程序的分析速度降低太多。,2020/8/4,北京化工大学信息科学与技术学院计算机系,66,4.2 Context-free grammars 上下文无关文法,2020/8/4,北京化工大学信息科学与技术学院计算机系,67,4.2.1 上下文无关文法概述, Comparison to regular expression notation与正则表达式 比较,the context-free grammar: number num

42、ber digit | digit ； digit 0 | 1 | 2 | 3 | | 9,the regular expression: number = digit digit* digit = 0|l|2|3|4|5l6|7|8|9,the context-free grammar: exp exp op exp | (exp) | number op + | | *,2020/8/4,北京化工大学信息科学与技术学院计算机系,68, Specification of context-free grammar rules 上下文无关文法规则的说明, 什么是文法？,文法是对语言

43、结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称“语法”）。,例:请判断英语句子The big elephant ate the peanut. 语法上是否正确？,2020/8/4,北京化工大学信息科学与技术学院计算机系,69, the big elephant | peanut ate ,解：,(1)已知语法规则,2020/8/4,北京化工大学信息科学与技术学院计算机系,70, = ,= ,= the ,= the big ,= the big elephant ,= the big elephant ,= the big elephant ate ,= the big

44、 elephant ate ,= the big elephant ate the ,= the big elephant ate the peanut,:= := :=the :=big :=elephant | peanut := :=ate :=,2020/8/4,北京化工大学信息科学与技术学院计算机系,71,Note,2020/8/4,北京化工大学信息科学与技术学院计算机系,72, Derivations and the language defined by a grammar 推导及由文法定义的语言,1. 相应的正则式：,2. derivation推导,例：根据文法，

45、请判断程序 (34-3)*42 语法上是否正确？ exp exp op exp | (exp) | number op + | | *,(1) exp = exp op exp exp exp op exp,(2) = exp op number exp number,(3) = exp * number op * ,(4) = ( exp ) * numberexp ( exp ) ,(5) = ( exp op exp ) * numberexp exp op exp,(6) = (exp op number) * number exp number,(7) = (exp - number

46、) * number op - ,(8) = (number - number) * number exp number,(number - number ) * number,2020/8/4,北京化工大学信息科学与技术学院计算机系,73,L(G) = s | exp = * s , 文法定义的（产生的）语言,exp ：开始符号 the start symbol = * ：星推导 (= + ：正推导) s ：句子,exp exp op exp | (exp) | number op + | | *,exp ：开始符号 the start symbol exp number： 产生式 Nont

47、erminals (非终结符) Terminals (终结符), 文法,2020/8/4,北京化工大学信息科学与技术学院计算机系,74, Example,1)已知文法G：E (E) | a ，请问文法定义的语言是什么？,L(G) = a,(a),(a),(a), = (na)n | n an integer = 0 ,2)已知文法G：E (E) ，请问文法定义的语言是什么？,空,3)已知文法G：E E + a | a ，请问文法定义的语言是什么？,L(G) =a, a + a ,a + a + a, a + a + a + a,.,4)已知正则式为a+ ，请问相应的文法及定义的语言是什么？,G

48、: A A a | a or A a A | a,L(a*) = an | n an integer = 0,5)已知正则式为a* ，请问相应的文法是什么？,G: A A a | or A a A | ,Recursive 递归 Grammar 文法 A A | A A | ,2020/8/4,北京化工大学信息科学与技术学院计算机系,75, Example,6) 已知文法定义的语言如下(C的嵌套if语句)，请写出该文法？ other if (0) other if (1) other if (0) other else other if (1) other else other,if (0)

49、if (0) other if (0) if (1) other else other if (1) other else if (0) other else other,2020/8/4,北京化工大学信息科学与技术学院计算机系,76, Example,7) 已知文法A (A) A | ，请问( ) ( ) ( ) 语法正确吗？,A = (A) AA (A) A = (A)(A)AA (A) A = (A)(A) A = (A)( ) A = (A)A)( ) A (A) A = ( ( )A)() A = ( ) (A)A ) () A (A) A = ( )(A) )( ) A = ( )

50、(A)A)( ) A (A) A = ( )( )A)( ) A = ( )( )( ) A ( ) ( ) ( ) 语法正确,2020/8/4,北京化工大学信息科学与技术学院计算机系,77, Example,8) 已知文法G如下 ，请问文法定义的语言是什么？ stmt-sequence stmt ; stmt-sequence | stmt stmt s,L(G)= s, s;s, s;s;s,. ),若例8中允许语句序列为空，则相应的文法是什么？,stmt-sequence stmt ; stmt-sequence | ? stmt s,若例8中允许语句序列为空，但要求分号作为语句分隔符，

51、 即定义的语言为 L(G)= , s, s;s, s;s;s,. ) ，则相应的 文法是什么？,stmt-sequence nonempty-stmt-sequence | nonempty-stmt-sequence stmt；nonempty-stmt-sequence | stmt stmt s,2020/8/4,北京化工大学信息科学与技术学院计算机系,78, Example,若例8中允许语句序列为空，但要求分号作为语句结束符， 即定义的语言为 L(G)= ;, s;, ;s;, s;s;, ;s;s;, s;s;s;,. ) ，则 相应的文法是什么？,stmt-sequence stm

52、t-other1 stmt-other2 stmt-other1 stmt | stmt-other2 ; stmt stmt-other2 | ; stmt s,2020/8/4,北京化工大学信息科学与技术学院计算机系,79,4.2.3 Parse trees and abstract syntax trees 分析树与抽象的语法树,(1) exp = exp op exp exp exp op exp (2) = (exp) op exp exp ( exp ) (3) = (exp op exp) op exp exp exp op exp (4) = (number op exp) o

53、p expexp number (5) = (number - exp) op expop - (6) = (number - number) op expexp number (7) = (number - number) * exp op * (8) = (number - number) * number exp number, derivation推导,最右 推导,最左 推导,2020/8/4,北京化工大学信息科学与技术学院计算机系,80,1) 推导,(1) exp = exp op exp (2) = number op exp (3) = number + exp (4) = nu

54、mber + number,(1) exp = exp op exp (2) = exp op number (3) = exp + number (4) = number + number, 分析树 (与推导相对应的作了标记的树),2) 分析树,(1) exp = exp op exp (2) = exp + exp (3) = number + exp (4) = number + number,exp,+,number,number,exp,+,number,number,exp,+,number,number,2020/8/4,北京化工大学信息科学与技术学院计算机系,81,(1) ex

55、p = exp op exp (2) = (exp) op exp (3) = (exp op exp) op exp (4) = (number op exp) op exp (5) = (number - exp) op exp (6) = (number - number) op exp (7) = (number - number) * exp (8) = (number - number) * number, derivation推导,2020/8/4,北京化工大学信息科学与技术学院计算机系,82,1) 表达式3+4的分析树：, Abstract syntax trees抽象语法树

56、(简称语法树),2) 语法树：,exp OpExp(op,exp,exp) | ConstExp(integer) op Plus | Minus | Times,3) 简单的算术表达式抽象语法树的文法:,例1：简单表达式的抽象语法树,解：,2020/8/4,北京化工大学信息科学与技术学院计算机系,83,4.2.4 Ambiguity 二义性, Ambiguous Grammars 二义性文法,例：已知简单整型算术文法， exp exp op exp|( exp ) | number op + | - | * 请画出串34-3*42 的语法树!,解： 1) 推导 2) 分析树 3

57、) 语法树,2020/8/4,北京化工大学信息科学与技术学院计算机系,84,解： 1)最左推导,例：已知简单整型算术文法 exp exp op exp|( exp ) | number op + | - | * 请画出串34-3*42 的分析树!,exp = exp op exp = exp op exp op exp = number op exp op exp =number - exp op exp = number - number op exp = number - number * exp = number - number * number and exp = exp op exp =number op exp =number - exp =number - exp op exp =number - number op exp =number - number * exp = number - number * number,2)分析树,2020/8/4,北京化工大学信息科学与技术学院计算机系,85,例：已知简单整型算术文法 exp exp op exp|( exp ) | number op + | - | * 请画出串34-3*42 的分析树!,3)语法树, ambiguous grammar 二义性文法,可生成两个不同分析树的串的文法叫二义性文法。