编译技术编译原理 (19).pdf

《编译技术编译原理 (19).pdf》由会员分享，可在线阅读，更多相关《编译技术编译原理 (19).pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译技术语 法 分 析本讲纲要语言和文法艾弗拉姆诺姆乔姆斯基（Avram Noam Chomsky，1928年12月7日），美国哲学家L1=wcw|w 属于(a|b)*L2=anbmcndm|n 0,m 0 标识符的声明应先于其引用的抽象语 言 和 文 法形参个数和实参个数应该相同的抽象L3=anbncn|n 0 早先排版描述的一个现象的抽象非 上 下 文 无 关 的 语 言 结 构 L1=wcwR|w(a|b)*S aSa|bSb|c 语 言 和 文 法有些类似的语言却是上下文无关的 L2 =anbmcmdn|n 1,m 1 S aSd|aAdA bAc|bc L2 =anbncmdm|n

2、1，m 1 S ABA aAb|abB cBd|cd L3=anbn|n 1 S aSb|ab语 言 和 文 法有些类似的语言却是上下文无关的 L3 是不能用正规式描述的语言的一个范例若存在接受L3 的DFA D，状态数为k个设D读完,a,aa,ak分别到达状态s0,s1,sk至少有两个状态相同，例如是si和sj，则ajbi属于L3 sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径文法 G=(VT,VN,S,P)0型文法：，,(VN VT)*,|1语 言 和 文 法1型文法：|，但S 可以例外形 式 语 言 鸟 瞰2型文法：A ，A VN,(V

3、N VT)*3型文法：A aB或A a，A,B VN,a VT短语文法、上下文有关文法、上下文无关文法、正规文法短语文法短语文法上下文有关上下文有关文法文法上下文无上下文无关文法关文法正规式正规式语 言 和 文 法例：L3anbncn|n 1的上下文有关文法S aSBCS aBCCB BCaB abbB bbbC bccC ccanbncn的推导过程如下：S*an-1S(BC)n 1用S aSBC n-1次S+an(BC)n用S aBC1次S+anBnCn用CB BC交换相邻的CBS+anbBn 1Cn用aB ab1次S+anbnCn用bB bbn-1次S+anbncCn-1用bC bc1次S+anbncn用cC ccn-1次编译技术语 法 分 析