高级语言及其文法

《高级语言及其文法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章高级语言及其文法（3）本章主要内容2.1语言概述2.2基本定义(语言、句子、形式化方法、串、字母表、串的连接与幂、产生式)2.3文法(Grammar)的定义2.4CFG的语法(分析)树(ParseTree)2.5文法的分类2.6文法的构造2.４文法的分类(Chomsky体系)语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG:PhraseStructureGrammar）。L(G)为PSL。2.4.1文法与语言的分类0型文法（或称短语

2、文法）特点：产生式行如α→β，α∈(VN∪VT)*且至少包含一个非终结符，而0型文法又称为无限制文法，有时也称为短语文法（phasestructuregrammar,PSG）。0型文法对应的语言称为0型语言或称递归可枚举集，它们的识别系统为图灵机（Turing机）。1型文法（或称上下文有关文法）特点：限制P中的每个产生式α→β都要满足

3、α

4、≤

5、β

6、。1型文法相对应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。1型文法的另一种定义方法是文法G(S)的每一个产生式具有下列形式：另一定义：2型文法（或

7、称上下文无关文法）特点：每个产生式的形式限制为A→β，其中A为单个非终结符，2型文法相对应的语言称为2型语言或上下文无关语言，它的识别系统为下推自动机(PDA)。3型文法（或称正规文法、正则文法）特点：文法中每个产生式的形式为A→aB或A→a，其中A、B∈VN，A、B、a都是单个符号。3型文法对应的语言称为3型语言或正规语言（正则语言，或正则集）。例2-3标识符的文法2S→L

8、LTT→L

9、N

10、TL

11、TNL→a

12、b

13、c

14、dN→0

15、1

16、2

17、3

18、4

19、5S→a

20、b

21、c

22、dS→aT

23、bT

24、cT

25、dTT→a

26、b

27、c

28、d

29、0

30、1

31、

32、2

33、3

34、4

35、5T→aT

36、bT

37、cT

38、dT

39、0TT→1T

40、2T

41、3T

42、4T

43、5T例2-4标识符的文法3S→a

44、b

45、c

46、dS→aT

47、bT

48、cT

49、dTT→a

50、b

51、c

52、dT→0

53、1

54、2

55、3

56、4

57、5T→aT

58、bT

59、cT

60、dT

61、0TT→1T

62、2T

63、3T

64、4T

65、5TS→a

66、b

67、c

68、dS→Ha

69、Hb

70、Hc

71、Hd

72、H0S→H1

73、H2

74、H3

75、H4

76、H5H→Ha

77、Hb

78、Hc

79、Hd

80、H0H→H1

81、H2

82、H3

83、H4

84、H5H→a

85、b

86、c

87、dA→aB或A→aA→Ba或A→a正规文法(RG)设A、B∈VN，a∈VT∪{}右线性(RightLi

88、near)文法：A→aB或A→a左线性(LeftLinear)文法：A→Ba或A→a都是３型文法(正规文法RegularGrammar-RG)L(G)为3型/正规集/正则集/正则语言（RL）例：程序设计语言的多数词法特性左、右线性文法不可混用例非CFL的文法L={anbncn

89、n>0}的文法SaBC

90、aSBCCBBCaBabbBbbbCbccCcc“可以证明”不存在CFGG,使L(G)=L在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。例L1={wcw

91、w∈{a,b}+}。例,aa

92、bcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。例L2={anbmcndm

93、n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。高级语言中的非CFL结构Chomsky体系——总结1型文法(CSG)SaBCSaSBCCBBCaBabbBbbbCbccCcc0型文法(PSG)SaBCSaSBCCBBCaBabbBbbbCbcCcc2型文法(CFG)E→E+EE→E*EE→(E)E→idE→E-EE→E/E3型文法S→a

94、bS→aT

95、

96、bTT→a

97、bT→1

98、2T→aT

99、bTT→1T

100、2T3型文法S→a

101、bS→Ha

102、HbS→H1

103、H2H→Ha

104、HbH→H1

105、H2H→a

106、bChomsky体系——总结Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β∈P*G是0型文法，L(G)是0型语言；---其能力相当于图灵机(TM)*

107、α

108、≤

109、β

110、:G是1型文法，L(G)是1型语言(除Ｓ→ε);---其识别系统是线性界限自动机(LBA)*α∈ＶN:G是2型文法，L(G)是2型语言;---其识别系统是不确定的下推自动机(PDA)*A→aB或A→a:G是右线性文法，L(G)

111、是3型语言A→Ba或A→ａ:G是左线性文法，L(G)是3型语言---其识别系统是有穷自动机(FA)四种文法之间的关系是将产生式作进一步限制而定义的四种文法之间的逐级“包含”关系如下：2型文法1型文法0型文法3型文法Chomsky体系——总结ＢＮＦ范式——Backus-NaurFormBackus-NormalFormα→β表示为α∷＝β非终结符用“<”和“