Chapter04SyntaxAnalysis语法分析.ppt

,北京化工大学 信息科学与技术学院计算机系 赵瑞莲 ,编译原理,2019/6/6,北京化工大学信息科学与技术学院计算机系,2,Chapter 4 Syntax Analysis语法分析,4.1 语法分析器的作用 4.2 上下文无关文法 4.3 自顶向下语法分析 4.4 自底向上语法分析,2019/6/6,北京化工大学信息科学与技术学院计算机系,3,4.1 语法分析器的作用,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成, The phase of a compiler 编译程序的结构,目 标 代 码 生 成,2019/6/6,北京化工大学信息科学与技术学院计算机系,4,4.1 语法分析器的作用,语法 分析器,词法 分析器,记号流,源程序,前端其他部分,分析树,中间表示,符号表管理器,出错处理器,2019/6/6,北京化工大学信息科学与技术学院计算机系,5, 源程序中可能出现的错误 词法错误如非法字符或拼写错关键字、标识符等； 如 intege 20times 语法错误是指语法结构出错，如少分号、begin/end不配对等。 begin x:=a+b y:=x;,4.1 语法分析器的作用,2019/6/6,北京化工大学信息科学与技术学院计算机系,6, 源程序中可能出现的错误 词法错误 语法错误 静态语义错误 动态语义错误（逻辑错误）,4.1 语法分析器的作用,如非法字符或拼写错关键字、标识符等； intege 20times,是指语法结构出错，如少分号、 begin/end不配对等。 begin x:=a+b； y:=x;,如无穷递归、变量为零时作除数等。 while (t) .; a:=a/b;,类型不一致、参数不匹配等； 如 a,b:integer; x:array110 of integer; x:=a+b;,2019/6/6,北京化工大学信息科学与技术学院计算机系,7, 语法错误处理的目标 清楚而准确地报告错误的出现 （地点正确、不漏报、不错报也不多报）； 迅速地从每个错误中恢复过来 （以便分析继续进行）； 不应使对语法正确源程序的分析速度降低太多。,4.1 语法分析器的作用,2019/6/6,北京化工大学信息科学与技术学院计算机系,8,4.2 Context-free grammars 上下文无关文法,2019/6/6,北京化工大学信息科学与技术学院计算机系,9,4.2.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 context-free grammar: exp exp op exp | (exp) | number op + | | *,2019/6/6,北京化工大学信息科学与技术学院计算机系,10, Specification of context-free grammar rules 上下文无关文法规则的说明, 什么是文法？,文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称“语法”）。,例:请判断英语句子The big elephant ate the peanut. 语法上是否正确？,2019/6/6,北京化工大学信息科学与技术学院计算机系,11, the big elephant | peanut ate ,解：,(1)已知语法规则,2019/6/6,北京化工大学信息科学与技术学院计算机系,12, = ,= ,= 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 :=,2019/6/6,北京化工大学信息科学与技术学院计算机系,13,Note,2019/6/6,北京化工大学信息科学与技术学院计算机系,14, 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 ) * number exp ( exp ) ,(5) = ( exp op exp ) * number exp exp op exp,(6) = (exp op number) * number exp number,(7) = (exp - number) * number op - ,(8) = (number - number) * number exp number,(number - number ) * number,2019/6/6,北京化工大学信息科学与技术学院计算机系,15,L(G) = s | exp = * s , 文法定义的（产生的）语言,exp ：开始符号 the start symbol = * ：星推导 (= + ：正推导) s ：句子,exp exp op exp | (exp) | number op + | | *,exp ：开始符号 the start symbol exp number： 产生式 Nonterminals (非终结符) Terminals (终结符), 文法,2019/6/6,北京化工大学信息科学与技术学院计算机系,16, 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: 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 | ,2019/6/6,北京化工大学信息科学与技术学院计算机系,17, 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) other if (0) if (1) other else other if (1) other else if (0) other else other,2019/6/6,北京化工大学信息科学与技术学院计算机系,18, Example,7) 已知文法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 ) () A (A) A = ( )(A) )( ) A = ( )(A)A)( ) A (A) A = ( )( )A)( ) A = ( )( )( ) A ( ) ( ) ( ) 语法正确,2019/6/6,北京化工大学信息科学与技术学院计算机系,19, Example,8) 已知文法G如下 ，请问文法定义的语言是什么？ stmt-sequence stmt ; stmt-sequence | stmt stmt s,L(G)= s, s;s, s;s;s,. ),若例8中允许语句序列为空，即定义的语言为 L(G)= , s;, s;s;, s;s;s;,. ) ，则相应的文法是什么？,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,2019/6/6,北京化工大学信息科学与技术学院计算机系,20, Example,若例8中允许语句序列为空，但要求分号作为语句结束符， 即定义的语言为 L(G)= ;, s;, ;s;, s;s;, ;s;s;, s;s;s;,. ) ，则 相应的文法是什么？,stmt-sequence stmt-other1 stmt-other2 stmt-other1 stmt | stmt-other2 ; stmt stmt-other2 | ; stmt s,2019/6/6,北京化工大学信息科学与技术学院计算机系,21,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) op exp exp number (5) = (number - exp) op exp op - (6) = (number - number) op exp exp number (7) = (number - number) * exp op * (8) = (number - number) * number exp number, derivation推导,最右 推导,最左 推导,2019/6/6,北京化工大学信息科学与技术学院计算机系,22,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,+,number,number,exp,+,number,number,exp,+,number,number,2019/6/6,北京化工大学信息科学与技术学院计算机系,23,(1) exp = 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推导,2019/6/6,北京化工大学信息科学与技术学院计算机系,24,1) 表达式3+4的分析树：, Abstract syntax trees抽象语法树 (简称语法树),2) 语法树：,exp OpExp(op,exp,exp) | ConstExp(integer) op Plus | Minus | Times,3) 简单的算术表达式抽象语法树的文法:,例1：简单表达式的抽象语法树,解：,2019/6/6,北京化工大学信息科学与技术学院计算机系,25,typedef enum Plus,Minus,Times OpKind typedef enum OpK.ConstK ExpKind; typedef struct streenode ExpKind kind; OpKind op; struct streenode *lchild,*rchild; int val; STreeNode; typedef STreeNode *SyntaxTree;,4) 简单的算术表达式抽象语法树的存储结构：,2019/6/6,北京化工大学信息科学与技术学院计算机系,26,解：分析树,例2：if语句的抽象语法树,1) 已知简化了的if语句的文法： statement if-stmt | other if-stmt if ( exp ) statement | if ( exp ) statement else statement exp 0 | 1 请画出串if (0) other else other的语法树!,2019/6/6,北京化工大学信息科学与技术学院计算机系,27,解：分析树,2)已知文法： statement if-stmt | other if-stmt if ( exp ) statement else-part else-part else statement | exp 0 | 1 请画出串if (0) other else other的语法树!,2019/6/6,北京化工大学信息科学与技术学院计算机系,28,3) if语句的抽象语法树：,4) if语句的存储表示：,typedef enum ExpK,StmtK) NodeKind; typedef enum Zero.One ExpKind; typedef enum IfK.OtherK) StmtKind; typedef struct streenode NodeKind kind; ExpKind ekind; . StmtKind skind; struct streenode *test,*thenpart,*elsepart; STreeNode; typedef STreeNode * SyntaxTree;,2019/6/6,北京化工大学信息科学与技术学院计算机系,29,解：分析,例3：顺序结构的语句的抽象语法树,1) 已知顺序结构的语句的文法： stmt-sequence stmt ; stmt-sequence | stmt stmt s 请画出串s; s; s的语法树!,stmt-sequence,;,stmt,stmt-sequence,s,;,stmt,s,s,stmt-sequence,stmt,2019/6/6,北京化工大学信息科学与技术学院计算机系,30,2)顺序结构的语句的抽象语法树,2019/6/6,北京化工大学信息科学与技术学院计算机系,31,4.2.4 Ambiguity 二义性, Ambiguous Grammars 二义性文法,例：已知简单整型算术文法， exp exp op exp|( exp ) | number op + | - | * 请画出串34-3*42 的语法树!,解： 1) 推导 2) 分析树 3) 语法树,2019/6/6,北京化工大学信息科学与技术学院计算机系,32,解： 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)分析树,2019/6/6,北京化工大学信息科学与技术学院计算机系,33,例：已知简单整型算术文法 exp exp op exp|( exp ) | number op + | - | * 请画出串34-3*42 的分析树!,3)语法树, ambiguous grammar 二义性文法,可生成两个不同分析树的串的文法叫二义性文法。, 消除二义性规则, 不修改文法，指定正确的分析树(或语法树)； 修改文法(优先级、结合性),2019/6/6,北京化工大学信息科学与技术学院计算机系,34, Precedence and associativity 优先级和结合性, precedence cascade 优先级联,具有相同优先级的算符归纳在一组，并为每一种优先级规定不同的规则。,例：将“乘法比加法和减法优先” 添加到简单的算术表达式文法。,exp exp addop exp | term addop + | - term term mulop term| factor mulop * factor ( exp ) | number,2019/6/6,北京化工大学信息科学与技术学院计算机系,35, 结合性,例：将“乘法比加法和减法优先，并且左结合” 添加到简单的算术表达式文法。,exp exp addop term |term addop + | - term term mulop factor | factor mulop * factor ( exp ) | number,exp exp addop exp | term,2019/6/6,北京化工大学信息科学与技术学院计算机系,36, The dangling else problem 悬挂else问题,例：文法是二义性文法吗？ statement if-stmt | other if-stmt if ( exp ) statement | if ( exp ) statement else statement exp 0 | 1,解：串if (0) if (1) other else other的分析树1：,2019/6/6,北京化工大学信息科学与技术学院计算机系,37,statement if-stmt | other if-stmt if ( exp ) statement | if ( exp ) statement else statement exp 0 | 1,串if (0) if (1) other else other的分析树2：,2019/6/6,北京化工大学信息科学与技术学院计算机系,38,statement if-stmt | other if-stmt if ( exp ) statement | if ( exp ) statement else statement exp 0 | 1, most closely nested rule用于悬挂else问题的最近嵌套规则 (消除二义性的规则),statement matched-stmt | unmatched-stmt matched-stmt if ( exp ) matched-stmt else matched-stmt | other unmatched-stmt if ( exp ) statement | if ( exp ) matched-stmt else unmatched-stmt exp 0 | 1,最近嵌套规则,matched-stmt：匹配的语句(不含不带else的if语句的语句)； unmatched-stmt：不匹配的语句(含不带else的if语句的语句)；,2019/6/6,北京化工大学信息科学与技术学院计算机系,39,statement if-stmt | other if-stmt if ( exp ) statement | if ( exp ) statement else statement exp 0 | 1, 消除二义性的规则方法2,if-stmt if condition then statement-sequence end if | if condition then statement-sequence else statement-sequence end if,2019/6/6,北京化工大学信息科学与技术学院计算机系,40, Inessential ambuguity 无关紧要二义性,文法有二义性，但总生成唯一的抽象的语法树。,例： 如下文法是无关紧要二义性文法！ stmt-sequence stint-sequence ; stmt-sequence | stmt stmt s,2019/6/6,北京化工大学信息科学与技术学院计算机系,41,4.2.5 extended notations: EBNF and syntax diagrams 扩展的表示法：EBNF和语法图, extended BNF, or EBNF表示法,1) 递归(重复：表示),左递归：A A | A * A ,右递归：A A | A * A ,文法,正则式,EBNF,2019/6/6,北京化工大学信息科学与技术学院计算机系,42,2) 选择( 表示 ),statement if-stmt | other if-stmt if ( exp ) statement else statement exp 0 | 1,例： stmt-Sequence stmt ; stmt-Sequence | stmt stmt s,解：stmt-sequence stmt ; stmt (right recursive form) stmt-sequence stmt ; stmt (left recursive form),例： stmt-sequence stmt; stmt-sequence | stmt,解：stmt-sequence stmt ; stmt-sequence ,2019/6/6,北京化工大学信息科学与技术学院计算机系,43,4.2.6 Formal properties of context-free language 上下文无关语言的形式特性, A formal definition of context-free language 上下文无关文法的形式定义 G = (T, N, P, S), A set T of terminals.（终结符集合T） A set N of nonterminals (disjoint from T) (非终极符集合N(与T不相交)） A set P of productions, or grammar rules, of the form A a, where A is an element of N and a is an element of (TN)* (产生式或文法规则A a集合P ，其中AN, a (TN)*) A start symbol S from the set N (开始(识别)符号 N),the set of symmbols(符号集)： TN TN A a ，其中|A|=1 | a |=0,注：,2019/6/6,北京化工大学信息科学与技术学院计算机系,44,P = ； ； ； 0； 1； 9； S = ；,例：无符号整数的文法如下，可否化简？ G=（N，T，P，S） N, T = 0,1,2,3,9,2019/6/6,北京化工大学信息科学与技术学院计算机系,45, 文法的简化方法：,产生式左边符号构成集合N，且 S N,具有相同的左部的产生式，可以合在一起,解：无符号整数的文法简化为：（产生式集合+开始符号）,G ； | ； 0 | 1 | 2 | 3 | | 9,2019/6/6,北京化工大学信息科学与技术学院计算机系,46, 文法G = (T, N, P, S) 的相关术语,G = (T, N, P, S)，其中v= a A ，w= a ，AN a, , (TN)* 若A P，则a A = a ，即v = w 称为v直接产生w(或w是v直接推导，或w直接规约到v),1) 直接推导,2019/6/6,北京化工大学信息科学与技术学院计算机系,47,2）+推导,G = (T, N, P, S)，a = a1， = an，其中a, (TN)* 若a1 = a2 a2 = a3 ，an-1 = an即a =+ 称为a推导出(产生) (推导长度为n) (或 规约到a),例： = = = = 1 = 1 0 即 =+ 10,G = (T, N, P, S)，a, (TN)* 若a =+ ，或a = 称为a推导出(产生) (推导长度为n) (或 规约到a ),2019/6/6,北京化工大学信息科学与技术学院计算机系,48,4） leftmost derivation最左推导,G = (T, N, P, S)，S=*w，每个推导步骤a A = a ，都有AN， , (TN)* ，aT* 称为S=*w为最左推导。,最左推导：若符号串中有两个以上的非终结符时，先推左边的。最右推导：若符号串中有两个以上的非终结符时，先推右边的。,5） rightmost derivation最右推导（规范推导）,G = (T, N, P, S)，S=*w，每个推导步骤a A = a ，都有AN， a , (TN)* ， T* 称为S=*w为最右推导。,2019/6/6,北京化工大学信息科学与技术学院计算机系,49,6） sentential form(句型),G = (T, N, P, S)，S=* a ，a (TN)* 称a为句型。,7） sentence (句子),G = (T, N, P, S)， S=* a ，a T* 称a为句子。,8） 文法产生的语言L(GS),G = (T, N, P, S)， L(GS)= a | S=* a ，a T* 称L(GS)为文法G产生的语言。,2019/6/6,北京化工大学信息科学与技术学院计算机系,50,9）短语、简单短语,G = (T, N, P, S)，w = xuy (TN)* 为文法的句型, 若S = xUy ,且 U =+ u, 则u是句型w相对于U 的短语； 若S = xUy, 且 U =u, 则u是句型w相对于U 的简单短语; 其中UN，u (TN)+ , x, y (TN)*,10）句柄,任一句型的最左简单短语称为该句型的句柄。,短语、简单短语是相对于句型而言， 一个句型可能有多个短语、简单短语，句柄只能有一个。,Note,2019/6/6,北京化工大学信息科学与技术学院计算机系,51, Example,E,T,F,i,F,解：E=*(E+T)*i+F (E+T)*i+F是G的一句型,2019/6/6,北京化工大学信息科学与技术学院计算机系,52,2019/6/6,北京化工大学信息科学与技术学院计算机系,53,11）文法G的分析树,1. Each node is labeled with a terminal or a nonterminal or . 2. The root node is labeled with the start symbol S. 3. Each leaf node is labeled with a terminal or with . 4. Each nonleaf node is labeled with a nonterminal. 5. If a node with label A N has n children with labels X1, X2,., Xn (which may be terminals or nonterminals), then A X1X2 . Xn P (a production of the grammar).,每个分析树只有唯一的一个最左推导和一个最右推导。 最左推导与分析树的前序编号相对应； 最右推导与分析树的后序编号相对应,Note,2019/6/6,北京化工大学信息科学与技术学院计算机系,54, The chomsky hierarchy 乔姆斯基层次,文法和语言分类：0型、1型、2型、3型（乔姆斯基层次）,2019/6/6,北京化工大学信息科学与技术学院计算机系,55,2019/6/6,北京化工大学信息科学与技术学院计算机系,56, 0型、1型、2型、3型比较, 3型：P：U t 或 U Wt 其中 U、WN tT, 2型： P：U v 其中U N ，v (TN)*, 0型：P：u v 其中u (TN)+ ，v (TN)*, 1型：P：xUy xuy 其中 UN， x,y,u (TN)*,L3 L2 L1 L0,附：自动机、正则文法、正则表达式 的相互转化,正则文法,NFA,正则表达式,1,2,3,4,5,6,DFA,最小化,（1）有穷自动机正则文法,1.对转换函数T(A,t)=B，可写成一个产生式:A tB,算法:,2.对可接受状态Z, 增加一个产生式: Z ,3.有穷自动机的初态对应于文法的开始符号, 有穷自动机的字母表为文法的终结符号集。,例:求出如图NFA等价的正则文法G。,1.对转换函数T(A,t)=B，可写成一个产生式:A tB,2.对可接受状态Z,增加一个产生式:Z ,3.有穷自动机的初态对应于文法的开始符号, 有穷自动机的字母表为文法的终结符号集。,（2）正则文法G 有穷自动机M,算法:,1.字母表与G的终结符号相同.,2.为G中的每个非终结符生成M的一个状态,G的开始符号S是开始状态S;,3.增加一个新状态Z,作为NFA的终态,4.对G中的形如A tB的产生式,其中t为终结符或,A和B为非终结符,构造M的一个转换函数f(A,t)=B,5.对G中的形如A t的产生式,构造M的一个转换函数f(A,t)=Z,例:求与文法GE等价的NFA GE: E aA|bB| A aB|bA B aE|bA|,解：,1.字母表与G的终结符号相同.,2.为G中的每个非终结符生成M的一个状态,G的开始符号S是开始状态S;,3.增加一个新状态Z,作为NFA的终态,4.对G中的形如A tB的产生式,其中t为终结符或,A和B为非终结符,构造M的一个转换函数f(A,t)=B,5.对G中的形如A t的产生式,构造M的一个转换函数f(A,t)=Z,（3）正则式 有穷自动机,1. (a)对于正则式,所构造NFA:,x,y,(b)对于正则式,所构造NFA:,x,y,(c)对于正则式a,a,则 NFA:,x,y,a,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,（4）有穷自动机 正则式,例:M如下，求相应的正则表达式。,解: ()加x,y ( 新的初态和终态 ),()消除M中的所有结点,解: ()加x,y ( 新的初态和终态 ),利用以下转换规则,直至只剩下一个开始符号定义的产 生式,并且产生式的右部不含非终结符.,规则,规则1,规则2,规则3,文法产生式,正则式,A xB,B y,A xA|y,A x,A y,A=xy,A=x*y,A=x|y,（5）正则文法 正则式,例:有文法Gs S aA|a A aA|dA|a|d 求相应的正则表达式,解: A=(aA|dA)|(a|d) =(a|d)A|(a|d) =(a|d)*(a|d) 代入规则1得： S=a(a|d)*(a|d)|a S=a(a|d)*(a|d)|),算法: 1) 对任何正则式r,选择一个非终结符S作为识别符号. 并产生产生式 S r 2) 若x,y是正则式,例: 将R=a(a|d)*转换成相应的正则文法,解:1) S a(a|d)*,2) S aA A(a|d)*,S aA A(a|d)A A ,S aA A aA|dA A ,（6）正则式 正则文法,规则,规则1,规则2,规则3,2019/6/6,北京化工大学信息科学与技术学院计算机系,70,4.2.7 Syntax of the TINY language TINY语言的语法,2019/6/6,北京化工大学信息科学与技术学院计算机系,71,program stmt-sequence stmt-sequence stmt-sequence ; statement | statement statement if-stmt | repeat-stmt | assign-stmt | read-stmt | write-stmt if-stmt if exp then stmt-sequence end | if exp then stmt-sequence else stmt-sequence end repeat-stmt repeat stmt-sequence until exp assign-stmt identifier := exp read-stmt read identifier write-stmt write exp exp simple-exp comparison-op simple-exp | simple-exp comparison-op | = simple-exp simple-exp addop term | term addop + | - term term mulop factor factor | factor mulop * | / factor (exp) |number |identifier, A context-free grammar for TINY,2019/6/6,北京化工大学信息科学与技术学院计算机系,72, TINY 基本结构类型：, Syntax tree structure for the TINY compiler,if-statements if语句 repeat-statements repeat语句 assign-statements assign语句 read-statements read语句 write-statements write语句,operator-expressions 算符表达式 constant-expressions 常量表达式 identifier-expression 标识符表达式,statements 语句 Expressions 表达式,2019/6/6,北京化工大学信息科学与技术学院计算机系,73, 语法树结构的图形描述,矩形：表示语句节点； 圆形和椭圆：表示表达式节点； 三角形：表示额外的非指定的树结构。,2019/6/6,北京化工大学信息科学与技术学院计算机系,74, 语法树结构的图形描述,2019/6/6,北京化工大学信息科学与技术学院计算机系,75,typedef enum StmtK, ExpK NodeKind; typedef enum IfK, RepeatK, AssignK, ReadK,WriteK StmtKind; typedef enum OpK, ConstK, IdK BxpKind; /* ExpType is used for type checking */ typedef enum Void, Integer, Boolean ExpType;, C declarations for a TINY syntax tree node,2019/6/6,北京化工大学信息科学与技术学院计算机系,76,#define MAXCHILDREN 3 typedef struct treeNode struct treeNode * childMAXCHILDREN; struct treeNode * sibling; int lineno; NodeKind nodekind; union StmtKind stmt; ExpKind exp; kind; union TokenType op; int val; char * name; attr; ExpType type; /* for type checking of exps */ TreeNode;,2019/6/6,北京化工大学信息科学与技术学院计算机系,77,4.3 Top -Down Parsing自顶向下的分析,4.3.1 TOP-DOWN PARSING BY RECURSIVE-DESCENT 使用递归下降分析算法进行自顶向下的分析 4.3.2 LL(1) PARSING LL(1)分析 4.3.3 FIRST AND FOLLOW SETS FIRST集合和FOLLOW集合,2019/6/6,北京化工大学信息科学与技术学院计算机系,78, Parsing 语法分析方法,Recursive-descent parsing递归下降法 LL(1) parsing LL(1)分析法,Backtracking parsers 回溯分析方法 Predictive parsers 预测分析方法,LR(0) parsing SLR(1) parsing LR(1) parsing LALR(1) parsing,2019/6/6,北京化工大学信息科学与技术学院计算机系,79,4.3.1 Top-down Parsing by Recursive-descent 使用递归下降分析算法进行自顶向下的分析, The idea of Recursive-Descent Parsing,递归下降法：将一个非终结符A的文法规则看作将识别A的一个过程的定义。,A的文法规则的右部指出此过程的代码结构。,2019/6/6,北京化工大学信息科学与技术学院计算机系,80,expr expr addop termterm addop + - term term mulop factor factor mulop * factor (expr) number, example,已知表达式文法， 及factor的文法规 则，使用递归下 降法识别factor。,2019/