编译原理ppt3_2.ppt

《编译原理ppt3_2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2语言和文法文法为语言给出了精确的、易于理解的语法说明对于某些文法类，可以自动产生高效的分析器如果文法设计得恰当，则它赋予语言的结构对于源程序翻译成正确的目标代码和对于错误诊断都是有用的语言也是逐步完善的，增加新构造以完成新任务的情况时有发生。如果存在以文法为基础的语言的实现，语言新构造的加入就显得方便文法能够描述程序设计语言的大部分语法成分，但不能描述程序设计语言的全部语法成分3.2.1正规式和上下文无关文法的比较正规表达式所描述的每一种结构都可以用上下文无关文法来描述例如描述正规表达式(a

2、b)*abb的上下文无关文法A0→aA0

3、bA0

4、aA1A1→bA2A2→εNFA--->上下

5、文无关文法对NFA的每个状态i，创建一个非终结符Ai如果状态i遇到输入符号a转换到状态j，则引入产生式Ai→aAj如果状态i遇到输入符号ε转换到状态j，则引入产生式Ai→Aj如果状态i是接受状态，则引入产生式Ai→ε如果状态i是开始状态，则Ai是文法的开始符号对任何a及A,BS，若有(A,a)=B，则：(a)当BF时，令A→aB，(b)当BF时，令A→a

6、aB。例：设DFAM=<{A,B,C,D},{0,1},,A,{B}>。M的状态转换图如下图所示，求等价的上下文无关文法ABCD100,1110G=<{0,1},{A,B,C,D},A,P>，其中P由下列产生式组成：A→0B

7、

8、1DB→0D

9、1C

10、εC→0B

11、1DD→0D

12、1DA→0

13、0B

14、1DB→0D

15、1CC→0

16、0B

17、1DD→0D

18、1D3.2.2分离词法分析器的理由为什么用正规式定义语言的词法，而不用上下文无关文法语言的词法规则简单正规式给出的描述更简洁且易于理解从正规式自动构造出的词法分析器更有效3.2.3验证文法产生的语言文法G产生语言L：由G产生的每个字符串都在L中；反之，L中的每个字符串都能由G产生例，下面的文法G能而且仅能产生所有配对的括号串S→(S)S

19、ε文法示例例1：G1[S]:S→bAA→aA

20、aL(G1)={ban

21、n≥1}例2：G2[S]:S→aSb

22、abL(G2)={anbn

23、n≥1}例3

24、：构造文法G3，使L(G3)={anbn+1

25、n≥0}G3[S]:S→aSb

26、b例4：构造文法G4，使L(G4)={ω

27、ω为字符集Σ上的回文}，Σ={a,b}G4[S]:S→aSa

28、bSb

29、a

30、b

31、ε3.2.4适当的表达式文法通过改写文法来消除文法的二义性例：G[expr]:expr→expr+expr

32、expr*expr

33、(expr)

34、id可以改写为如下无二义文法expr→expr+term

35、termterm→term*factor

36、factorfactor→(expr)

37、id将相同优先权的算符放在一组，并为每一种优先权规定不同的规则E→E+E

38、TT→T*T

39、FF→(E)

40、i文法中仍为指定

41、算符的结合性，还具有二义性，用基本情况代替递归，强制重复算符匹配一边的递归将规则E→E+E

42、T替换为E→E+T

43、T(左结合)E→T+E

44、T(右结合)最后得到:G'[E]E→E+T

45、TT→T*F

46、FF→(E)

47、i3.2.5消除二义性例stmt→ifexprthenstmt

48、ifexprthenstmtelsestmt

49、other考虑：ifE1thenifE2thenS1elseS2每个else和前面最近的没有配对的then配对基本思想：出现在then和else之间的语句必须是“配对”的，即它不能以一个未配对的then后面跟随任意的非else语句结束，于是else会被迫与这个未配对的then匹配

50、。改写后的文法stmt→matched_stmt

51、unmatched_stmtmatched_stmt→ifexprthenmatched_stmtelsematched_stmt

52、otherunmatched_stmt→ifexprthenstmt

53、ifexprthenmatched_stmtelseunmatched_stmt3.2.6消除左递归一个文法是含有左递归的，如果存在非终结符A，存在推导消除直接左递归将规则A→A

54、（其中不以A开头）改写为：A→A'A→A

55、例：文法E→E+T

56、TT→T*F

57、FF→(E)

58、id消除左递归E→TE'E'→+TE'

59、εT→FT'T'→*

60、FT'

61、εF→(E)

62、id一般形式的直接左递归A→Aα1

63、Aα2

64、...

65、Aαm

66、β1

67、β2

68、...

69、βn消除A的左递归A→β1A'

70、β2A'

71、...

72、βnA'A'→α1A'

73、α2A'

74、...

75、αmA'

76、ε例如文法G[S]S→Aa

77、bA→Ac

78、Sd

79、ε虽没有直接左递归，但S、A都是左递归的SAaSda消除左递归的算法(1)把文法G的所有非终结符按任一顺序排列成A1,A2,...An；按此顺序执行(2)FO