《打印词法分析和语法分析.ppt》由会员分享，可在线阅读，更多相关《打印词法分析和语法分析.ppt（224页珍藏版）》请在三一办公上搜索。
1、2023/10/7,北京化工大学信息科学与技术学院计算机系,1,Chapter 3 Scanning(lexical analysis)词法分析,3.1 词法分析器的作用3.2 记号的描述3.3 记号的识别3.4 从正规表达式到DFA3.5 TINY扫描程序的实现3.6 LEX,2023/10/7,北京化工大学信息科学与技术学院计算机系,2,3.1 词法分析器的作用,词法分析,源程序,目标程序,语法分析,语义分析,中间代码优化,中间代码生成,The phase of a compiler 编译程序的结构,目标代码生成,2023/10/7,北京化工大学信息科学与技术学院计算机系,3,3.1 词法
2、分析器的作用,读入输入字符，产生记号序列，供语法分析使用3.1.1 词法分析中的问题3.1.2 记号3.1.3 记号的属性,2023/10/7,北京化工大学信息科学与技术学院计算机系,4,3.1 词法分析器的作用,3.1.1 词法分析中的问题,把编译过程的分析阶段划分为词法分析和语法分析的原因如下：1.简化编译器的设计可能是最重要的考虑。2.提高编译器的效率。3.增强编译器的可移植性。,2023/10/7,北京化工大学信息科学与技术学院计算机系,5,3.1 词法分析器的作用,3.1.2 记号:扫描程序生成的逻辑单元,以字母开头：保留字：IF,THEN,ELSE,END,REPEAT,UNTIL
3、,READ,WRITE标识符：字母/数字串以数字开头：整常数：数字开头的数字串实常数：整数.整数符号词：+，-，*，/，(，)，:，:=，;，.控制词：enter,Reserved Words保留字,2023/10/7,北京化工大学信息科学与技术学院计算机系,6,typedef enum/*book-keeping tokens*/ENDFILE,ERROR,/*reserved words*/IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE,/*multicharacter tokens*/ID,NUM,/*special symbols*/ASSIGN,EQ
4、,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI TokenType;,Tokens(记号)的枚举表示,每一个记号的表示：Typedef struct TokenType tokenval;char*stringval;int numval;TokenRecord,2023/10/7,北京化工大学信息科学与技术学院计算机系,7,3.1.3记号的属性任何与记号相关的值E=M*C,3.1 词法分析器的作用,2023/10/7,北京化工大学信息科学与技术学院计算机系,8,3.2 记号的描述,be set of the ASCII characters or s
5、ome subset of it,3.2.1 串和语言3.2.2 语言上的运算,2023/10/7,北京化工大学信息科学与技术学院计算机系,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:matches no string at all,whose language is the empty set.L()=,3.2.3 Definition of Regular
6、 Expression,1.Basic Regular Expression 基本正则表达式,2023/10/7,北京化工大学信息科学与技术学院计算机系,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，(a|bb)*=？L(a|bb)*)=？,2023/10/7,北京化工大学信息科学与技术学院计算机系,11,Names for regular expression 正则表达式的名字,Precedence
7、of Operation and use of parentheses 运算符的优先级和括号的使用,Precedence of Operation运算符的优先级,Precedence:*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|9digit digit*,2023/10/7,北京化工大学信息科学与技术学院计算机系,12,3.Example,1)=a,b,c the set of all strings ov
8、er this alphabet that contain exactly one b.(上只包括一个b的所有串的集合),(a|c)*b(a|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的
9、集合),S=b,aba,aabaa,aaabaaa,“regular expression cant count”,2023/10/7,北京化工大学信息科学与技术学院计算机系,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 conci
10、se English description 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*,2023/10/7,北京化工大学信息科学与技术学院计算机系,14,3.2.4 Extensions to Regular Expressions,r?the strings matched by r are optional,1.one or more repetitions 一个或多个重复(正闭包),r
11、+,2.any character 任意字符,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 可选的表达式,2023/10/7,北京化工大学信息科学与技术学院计算机系,15,Regular Expressions for Programming Language Tokens,1
12、.Numbers 数,nat=0-9+signedNat=(+|-)?natnumber=signedNat(“”nat)?(E signedNat)?,2.Reserved Words and Identifiers 保留字和标识符,reserved=if|while|do|letter=a-z A-Zdigit=0-9identifier=letter(letter|digit)*,3.Comments 注释,/*this is a C comment*/this is a pascal comment,4.Ambiguity,White Space,and Lookahead 二义性、空
13、格、回溯,2023/10/7,北京化工大学信息科学与技术学院计算机系,16,3.2.5 正则文法,2023/10/7,北京化工大学信息科学与技术学院计算机系,17,3.3 记号的识别,状态转换图有穷自动机,2023/10/7,北京化工大学信息科学与技术学院计算机系,18,3.3.1 状态转换图,状态转换图的表示方法,结点代表状态(state)，用圆圈表示。状态之间用箭弧(transition)连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。一个有穷自动机只包含有限个状态(即有限个结点)，其中一个为初态(start state)，至少一个为终态(接受状态
14、accepting state)(双圈表示)。,2023/10/7,北京化工大学信息科学与技术学院计算机系,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 automation(NFA)非确定有穷自动机,2023/1
15、0/7,北京化工大学信息科学与技术学院计算机系,20,3.3.2.1 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 states S 有穷状态集（非终极符集合）a transition function T:S S(状态转换函数)
16、a start state s0S 唯一的初始状态 a set of accepting states A S 终止状态集,2023/10/7,北京化工大学信息科学与技术学院计算机系,21,Example,1)exactly one b.(上只包括一个b的所有串的集合),2)most one b.(上最多包括一个b的所有串的集合),(not b)*b(not b)*,(not b)*(b|)(not b)*,2023/10/7,北京化工大学信息科学与技术学院计算机系,22,Example,3)digit=0-9nat=digit+signedNat=(+|-)?NatNumber=singed
17、Nat(“.”nat)?(E signedNat)?,2023/10/7,北京化工大学信息科学与技术学院计算机系,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)的值，这个矩阵称状态表（状态转移矩阵）。,状态,输入字符,后继状态,状态表,2023/10/7,北京化工大学信息科学与技术学院计算机系,24,3.3.2.2
18、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 transition function T:S x(U)(S)(状态转换函数)a set of start states S0 S 初始状态集 a set of accepting states A S 终止状态
19、集,2023/10/7,北京化工大学信息科学与技术学院计算机系,25,2023/10/7,北京化工大学信息科学与技术学院计算机系,26,DFA,NFA,2023/10/7,北京化工大学信息科学与技术学院计算机系,27,3.3.2.3 Implementation of finite automata in Code 用代码实现有穷自动机,识别标识符的DFA（方法1）：,starting in state 1 if the next character is a letter then advance the input;now in state 2 while the next charact
20、er 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;,2023/10/7,北京化工大学信息科学与技术学院计算机系,28,识别标识符的DFA（方法2）：,state:=1;ch:=next input character;while not Acceptstote and not error(state)do newstate:=Tstate
21、,ch;if Advancestate,ch then ch:=next input character;state:=newstate;end while;if Acceptstate then accept;,2023/10/7,北京化工大学信息科学与技术学院计算机系,29,3.4 From Regular Expression To DFAs从正则表达式到DFA,1.(a)对于正则式,所构造NFA:,x,y,(b)对于正则式,所构造NFA:,x,y,(c)对于正则式a,a,则 NFA:,x,y,a,the algorithm:translating a regular expressio
22、n into a DFA,3.5.1 从正则表达式到NFA,2023/10/7,北京化工大学信息科学与技术学院计算机系,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=S的NFA一样.,例:为R=(a|b)*abb构造NFA,使得L(N)=L(R),分解R的方法有很多种！,R=(a|b)*abb,2023/10/7,北京化工大学信息科学与技术学院计算机系,33,从正则表达式到NFA 方法二:,AB,i,A,B,i,k,A|B,
23、i,A*,i,A,B,i,i,k,A,NFA替换规则(NFA允许边出现),2023/10/7,北京化工大学信息科学与技术学院计算机系,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,7)其中T如上（不可省略）,初态,终态,(a|b)*(aa|bb)(a|b)*,2023/10/7,北京化工大学信息科学与技术学院计算机系,35,非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的,NFA M,DFA M,构造成一个,使得 L(M)=L(M),3.4.2
24、 从NFA到DFA,2023/10/7,北京化工大学信息科学与技术学院计算机系,36,（）合并（如果有S1S2,则把S2状态合并到S1状态）符号合并,NFA允许边出现,NFA到DFA的区别：,转换思想：,2023/10/7,北京化工大学信息科学与技术学院计算机系,37,例1：NFA转换成DFA(符号合并),解：根据题意，得出相应的正则式：0(0|1)*1 得状态转换图(NFA)如下：,2023/10/7,北京化工大学信息科学与技术学院计算机系,38,NFA确定为DFA过程：DFA的初态（为NFA的初始状态经过合并后的状态的并集）例：T(S,)=;DFA的其它状态（为NFA的状态经过输入符号后产
25、生的状态，再经过合并后的状态的并集）例：求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,2023/10/7,北京化工大学信息科学与技术学院计算机系,39,NFA确定化过程：(初态、其它状态、终态),0,1,0,C,S,A,B,1,2023/10/7,北京化工大学信息科学与技术学院计算机系,40,得状态转换图(DFA)如下：,在DFA中，所有含有NFA的终态的状态作为DFA的终态,DFA M=(S,A,B,C,0,1,T,S,C)其中T如上（不可省略）,2023/10/7,北京化工大学
26、信息科学与技术学院计算机系,41,定义1：状态集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为：1）若sI，则s-closure（I）；2）若sI，则从s出发经过任意条弧能够到达的任何状态都属于-closure（I）。状态集-closure（I）称为I的-闭包,为了使得NFA确定化，给出两个定义：,解：根据定义：-closure（I）=1，3,2023/10/7,北京化工大学信息科学与技术学院计算机系,42,J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合。,Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过弧到达的状态。,定义2:状态子集
27、的构造：,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),2023/10/7,北京化工大学信息科学与技术学院计算机系,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=
28、2,3,Ia=2,Ib=4,Ic=3,4,1,4,2023/10/7,北京化工大学信息科学与技术学院计算机系,44,DFA M状态表,将求得的状态转换矩阵重新编号,2023/10/7,北京化工大学信息科学与技术学院计算机系,45,“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”一个有穷自动机是化简的 没有多余状态 并且 状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。,3.4.3 DFA的化简(极小化),2023/10/7,北京化工大学信息科学与技术学院计算机系,46,有穷自动机的多余状态：从该自动机的开始状态出发，
29、任何输入串也不能到达那个状态。,2023/10/7,北京化工大学信息科学与技术学院计算机系,47,(2)等价状态 状态s和t的等价条件是:,1)一致性条件：状态s和t必须同时为可接受状态或不接受状态.2)蔓延性条件：对于所有输入符号,状态s和t必须转换到等价的状态里.,对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同的后继，则称s，t是等价的。（任何有后继的状态和任何无后继的状态一定不等价）,有穷自动机的状态s和t不等价,称这两个状态是可区别的。,2023/10/7,北京化工大学信息科学与技术学院计算机系,48,“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相
30、关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.,最小化DFA的方法：,2023/10/7,北京化工大学信息科学与技术学院计算机系,49,解:,(一)区分终态与非终态,a,b,2,4,3,1,srart,a,a,a,a,a,a,a,b,b,b,b,b,b,b,2023/10/7,北京化工大学信息科学与技术学院计算机系,50,区号,区号,2023/10/7,北京化工大学信息科学与技术学院计算机系,51,例2：设计一个最小化的DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。化简,DFA M=(S,ABC,BCZ,0,1,T,S,BCZ)其中
31、T如上(不可省略),2023/10/7,北京化工大学信息科学与技术学院计算机系,52,例3：试求与下图所示NFA等价的化简了的DFA。,0,0,3,1,1,2,4,0,1,1,0,1,0,1,0,1,化简后的DFA:,2023/10/7,北京化工大学信息科学与技术学院计算机系,53,例4：试构造与正则式R=(a*|b*)b(ba)*等价的状态最少的DFA。,2023/10/7,北京化工大学信息科学与技术学院计算机系,54,NFA确定为DFA:,注：状态从18标注,2023/10/7,北京化工大学信息科学与技术学院计算机系,55,3.5 Implementation of a tiny scan
32、ner TINY扫描程序的实现,The tokens and token classes of TINY,Reserved Words Special Symbols Otherif+numberthen-(1 or more digits)else*end/repeat=until identifierread(1 or more letters)write);:=,:Comments,2023/10/7,北京化工大学信息科学与技术学院计算机系,56,The DFA 1 for the special symbols except assignment,The DFA 2(numbers a
33、nd identifiers),2023/10/7,北京化工大学信息科学与技术学院计算机系,57,The DFA 3(comments,white space,assignment),2023/10/7,北京化工大学信息科学与技术学院计算机系,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
34、-1until x=0;write fact output factorial of x end,2023/10/7,北京化工大学信息科学与技术学院计算机系,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:i
35、f 6:mum,val=0 6:6:id,name=x6:reserved word:then,7:fact:=1;7:id,name=fact 7:=7:num,val=17:|;8:repeat8:reserved word:repeat 9:fact:=fact*x;9:id,name=fact 9:=9:id,name=fact 9:*9:id,name=x9:;,2023/10/7,北京化工大学信息科学与技术学院计算机系,60,Output of scanner,10:x:=x-1 10:id,name=x 10:=10:id,name=x 10:-10:mum,val=1 11:u
36、ntil 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,2023/10/7,北京化工大学信息科学与技术学院计算机系,61,Chapter 4 Syntax Analysis语法分析,4.1 语法分析器的作用4.2 上下文无关文法 4.3自顶向下语法分析4.4自底向上语法分析,2023/10/7,北京化
37、工大学信息科学与技术学院计算机系,62,4.1 语法分析器的作用,词法分析,源程序,目标程序,语法分析,语义分析,中间代码优化,中间代码生成,The phase of a compiler 编译程序的结构,目标代码生成,2023/10/7,北京化工大学信息科学与技术学院计算机系,63,4.1 语法分析器的作用,语法分析器,词法分析器,记号流,源程序,前端其他部分,分析树,中间表示,符号表管理器,出错处理器,2023/10/7,北京化工大学信息科学与技术学院计算机系,64,4.1.1 语法错误的处理,源程序中可能出现的错误 词法错误如非法字符或拼写错关键字、标识符等；20times:语法错误是指
38、语法结构出错，如少分号、begin/end不配对等。beginx:=a+by:=x;静态语义错误：如类型不一致、参数不匹配等；a,b:integer;x:array1.10 of integer;x:=a+b;动态语义错误（逻辑错误）：如无穷递归、变量为零时作除数等。while(t).;a:=a/b;,2023/10/7,北京化工大学信息科学与技术学院计算机系,65,4.1.1 语法错误的处理,语法错误处理的目标 清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；迅速地从每个错误中恢复过来（以便分析继续进行）；不应使对语法正确源程序的分析速度降低太多。,2023/10/7,北京化工
39、大学信息科学与技术学院计算机系,66,4.2 Context-free grammars 上下文无关文法,2023/10/7,北京化工大学信息科学与技术学院计算机系,67,4.2.1 上下文无关文法概述,4.2.1.1 Comparison to regular expression notation与正则表达式比较,the context-free grammar:number number 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 c
40、ontext-free grammar:exp exp op exp|(exp)|numberop+|*,2023/10/7,北京化工大学信息科学与技术学院计算机系,68,4.2.2.1 Specification of context-free grammar rules 上下文无关文法规则的说明,什么是文法？,文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称“语法”）。,例:请判断英语句子The big elephant ate the peanut.语法上是否正确？,2023/10/7,北京化工大学信息科学与技术学院计算机系,69,the big ele
41、phant|peanut ate,解：,(1)已知语法规则,2023/10/7,北京化工大学信息科学与技术学院计算机系,70,=,=,=the,=the big,=the big elephant,=the big elephant,=the big elephant ate,=the big elephant ate,=the big elephant ate the,=the big elephant ate the peanut,:=:=:=the:=big:=elephant|peanut:=:=ate:=,2023/10/7,北京化工大学信息科学与技术学院计算机系,71,Note,2
42、023/10/7,北京化工大学信息科学与技术学院计算机系,72,4.2.2.2 Derivations and the language defined by a grammar 推导及由文法定义的语言,1.相应的正则式：,2.derivation推导,例：根据文法，请判断程序(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)
43、=(exp op exp)*numberexp exp op exp,(6)=(exp op number)*number exp number,(7)=(exp-number)*number op-,(8)=(number-number)*number exp number,(number-number)*number,2023/10/7,北京化工大学信息科学与技术学院计算机系,73,L(G)=s|exp=*s,文法定义的（产生的）语言,exp：开始符号 the start symbol=*：星推导(=+：正推导)s：句子,exp exp op exp|(exp)|numberop+|*,e
44、xp：开始符号 the start symbolexp number：产生式Nonterminals(非终结符)Terminals(终结符),文法,2023/10/7,北京化工大学信息科学与技术学院计算机系,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+，请问相应的文法及定义的语言是什么？,
45、G: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|,2023/10/7,北京化工大学信息科学与技术学院计算机系,75,Example,6)已知文法定义的语言如下(C的嵌套if语句)，请写出该文法？other if(0)other if(1)other if(0)other else other if(1)other else other,if(0)if(0)otherif(0)if(1)other else oth
46、erif(1)other else if(0)other else other,2023/10/7,北京化工大学信息科学与技术学院计算机系,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=()(A)A)()A(A)A=()()A)()A=()()()A()()()语法正确,2023/10/7,北京化工大学信息科学与技术学院计算机系,77,Example,8)已知文法G如下，请问文法定义的语言是什么
47、？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中允许语句序列为空，但要求分号作为语句分隔符，即定义的语言为 L(G)=,s,s;s,s;s;s,.)，则相应的 文法是什么？,stmt-sequence nonempty-stmt-sequence|nonempty-stmt-sequence stmt；nonempty-stmt-sequence|stmt stmt s,20
48、23/10/7,北京化工大学信息科学与技术学院计算机系,78,Example,若例8中允许语句序列为空，但要求分号作为语句结束符，即定义的语言为 L(G)=;,s;,;s;,s;s;,;s;s;,s;s;s;,.)，则 相应的文法是什么？,stmt-sequence stmt-other1 stmt-other2stmt-other1 stmt|stmt-other2;stmt stmt-other2|;stmt s,2023/10/7,北京化工大学信息科学与技术学院计算机系,79,4.2.3 Parse trees and abstract syntax trees 分析树与抽象的语法树,(
49、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)op 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推导,最右推导,最左推导,2023/10/7,北京化工大学信息科学与技术学院
50、计算机系,80,1)推导,(1)exp=exp op exp(2)=number op exp(3)=number+exp(4)=number+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,exp,exp,2023/10/7,北京化工大学信息科学与技术学院计算机系,81,(1)exp=exp op exp(2)=(exp
