《chapter04syntaxanalysis语法分析》由会员分享，可在线阅读，更多相关《chapter04syntaxanalysis语法分析（124页珍藏版）》请在金锄头文库上搜索。
1、,北京化工大学 信息科学与技术学院计算机系 赵瑞莲 ,编译原理,2019/1/29,北京化工大学信息科学与技术学院计算机系,2,Chapter 4 Syntax Analysis语法分析,4.1 语法分析器的作用 4.2 上下文无关文法 4.3 自顶向下语法分析 4.4 自底向上语法分析,2019/1/29,北京化工大学信息科学与技术学院计算机系,3,4.1 语法分析器的作用,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成, The phase of a compiler 编译程序的结构,目 标 代 码 生 成,201
2、9/1/29,北京化工大学信息科学与技术学院计算机系,4,4.1 语法分析器的作用,语法 分析器,词法 分析器,记号流,源程序,前端其他部分,分析树,中间表示,符号表管理器,出错处理器,2019/1/29,北京化工大学信息科学与技术学院计算机系,5, 源程序中可能出现的错误 词法错误如非法字符或拼写错关键字、标识符等； 如 intege 20times 语法错误是指语法结构出错，如少分号、begin/end不配对等。 begin x:=a+b y:=x;,4.1 语法分析器的作用,2019/1/29,北京化工大学信息科学与技术学院计算机系,6, 源程序中可能出现的错误 词法错误 语法错误 静态
3、语义错误 动态语义错误（逻辑错误）,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/1/29,北京化工大学信息科学与技术学院计算机系,7, 语法错误处理的目标 清楚而准确地报告错误的出现 （地点正确、不漏报、不错报也不多报）； 迅速地从每个错误中恢
4、复过来 （以便分析继续进行）； 不应使对语法正确源程序的分析速度降低太多。,4.1 语法分析器的作用,2019/1/29,北京化工大学信息科学与技术学院计算机系,8,4.2 Context-free grammars 上下文无关文法,2019/1/29,北京化工大学信息科学与技术学院计算机系,9,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 |
5、 | 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/1/29,北京化工大学信息科学与技术学院计算机系,10,4.2.2.1 Specification of context-free grammar rules 上下文无关文法规则的说明, 什么是文法？,文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称“语法”）
6、。,例:请判断英语句子The big elephant ate the peanut. 语法上是否正确？,2019/1/29,北京化工大学信息科学与技术学院计算机系,11, the big elephant | peanut ate ,解：,(1)已知语法规则,2019/1/29,北京化工大学信息科学与技术学院计算机系,12, = ,= ,= the ,= the big ,= the big elephant ,= the big elephant ,= the big elephant ate ,= the big elephant ate ,= the big elephant ate
7、the ,= the big elephant ate the peanut,:= := :=the :=big :=elephant | peanut := :=ate :=,2019/1/29,北京化工大学信息科学与技术学院计算机系,13,Note,2019/1/29,北京化工大学信息科学与技术学院计算机系,14,4.2.2.2 Derivations and the language defined by a grammar 推导及由文法定义的语言,1. 相应的正则式：,2. derivation推导,例：根据文法，请判断程序 (34-3)*42 语法上是否正确？ exp exp op
8、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 - n
9、umber) * number exp number,(number - number ) * number,2019/1/29,北京化工大学信息科学与技术学院计算机系,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 (终结符),
10、文法,2019/1/29,北京化工大学信息科学与技术学院计算机系,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*) =
11、 an | n an integer = 0,5)已知正则式为a* ，请问相应的文法是什么？,G: A A a | or A a A | ,Recursive 递归 Grammar 文法 A A | A A | ,2019/1/29,北京化工大学信息科学与技术学院计算机系,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) othe
12、r else other if (1) other else if (0) other else other,2019/1/29,北京化工大学信息科学与技术学院计算机系,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)(
13、 ) A = ( )( )( ) A ( ) ( ) ( ) 语法正确,2019/1/29,北京化工大学信息科学与技术学院计算机系,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中允许语句序列为空，但要求分
14、号作为语句分隔符， 即定义的语言为 L(G)= , s, s;s, s;s;s,. ) ，则相应的 文法是什么？,stmt-sequence nonempty-stmt-sequence | nonempty-stmt-sequence stmt；nonempty-stmt-sequence | stmt stmt s,2019/1/29,北京化工大学信息科学与技术学院计算机系,20, Example,若例8中允许语句序列为空，但要求分号作为语句结束符， 即定义的语言为 L(G)= ;, s;, ;s;, s;s;, ;s;s;, s;s;s;,. ) ，则 相应的文法是什么？,stmt-se
15、quence stmt-other1 stmt-other2 stmt-other1 stmt | stmt-other2 ; stmt stmt-other2 | ; stmt s,2019/1/29,北京化工大学信息科学与技术学院计算机系,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)
