编译原理 教学课件 作者 康慕宁 林奕 讲稿_3.ppt

《编译原理 教学课件 作者 康慕宁 林奕 讲稿_3.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章语法分析与前后文无关文法基本知识编译程序的扫描器从输入的源程序字符流中识别出程序设计语言的单词，即语言中的终结符号。由扫描器所定义的语言是单词的集合，即词法级的程序设计语言。语法分析程序实际上是一个下推自动机（PDA:Push-DownAutomata），它识别一个语言的短语结构——语言的单词如何组合成语法正确的程序。多数程序设计语言允许嵌套的句法结构，这样的语言可由前后文无关文法定义，因此被称为前后文无关语言（CFL:Context-FreeLanguage）。事实上，每个PDA识别的语言都是CFL。这个结论可由本章将要介绍的从PDA构造CFG（Context-FreeGramm

2、ar）的规则得出。由PDA接受的语言相应CFG的每个产生式与PDA的一个转换对应。本章主要内容由确定的PDA接受的、被称为是由LL(1)文法定义的语言。LL(1)语言可由确定的、自顶向下的分析程序识别，且在识别过程中，每次最多向前搜索1个输入符号即可确定下一步的分析动作。LL分析表示自左至右扫描、最左推导（fromLefttoRightandLeftmostDerivation）的语法分析。我们还将介绍一种目前最常用的一种自底向上的语法分析文法——LR分析法。3.1下推自动机(Push-DownAutomata)【定义3·1】一个下推自动机形式上被定义为一个七元组：其中，：输入符号表；Q

3、：有限状态集合；H：下推栈字母表；h0（∈H）：开始符号，即开始时下推栈中放置的符号；q0（∈Q）：开始状态；F（Q）：终止状态集；：Q×({})×HQ×H*是描述状态转换的函数。转换函数的含义输入符号表元素可以作为栈符号表元素（H），栈可以有任意的深度。转换规则集是从状态集、输入符号集、栈符号集到状态及栈符号串的部分函数。每步转换都将从栈中顶出一个符号，并重新将零个或多个栈符号压入栈。转换规则与有限自动机的转换规则类似，如该转换规则表示，在当前状态qi下，输入符号为a，栈顶符号为X，则将当前状态转换为qj,读写头向前挪动一格，将栈顶符号X顶出栈，并将栈符号串压入栈

4、(压入栈顺序是逆向的，后面会解释)。我们用格局（q,,）下推自动机的当前的运行状态，其中，q表示状态，表示尚未识别的输入符号串，表示当前栈内的符号串。PDA的终止（停机）可有两种方式1）空栈方式在扫描完输入串时，若栈内为空，则PDA终止；2）终态方式若输入串扫描完毕且栈顶状态是一个终止状态（∈F），则PDA终止。对于以上两种终止方式，PDA均接受输入。若PDA在未达到终态或未空栈情况下扫描完输入串，则拒绝该输入。非确定的PDA与FA一样，PDA也可以是非确定的。非确定的PDA与确定的PDA的区别在于，对于任何给定的格局，它有多于一个的可能转换规则。PDA实例【例3·1】设P0=({

5、a,b,c},{A,B,C},,{h,i},i,A,)是一确定的下推自动机，其中，的定义如下：(A,a,i)=(B,h);(A,c,i)=(A,);(B,a,h)=(B,hh);(B,c,h)=(C,h);(C,b,h)=(C,)PDAP0识别所有由文法{S→aSb

6、c}定义的语言的句子（符号串），即由c隔开的相等个数的a与b组成的符号串。图3-1中描述了PDAP0识别输入符号串aacbb的过程中，当其扫描到输入字符c时的状态。P0识别aacbb的整个识别过程见图3-2所示。图3.2中的格局变化我们还可以用如下简易的方法描述：(A,aacbb,i)(B,acbb,h)

7、(B,cbb,hh)(C,bb,hh)(C,b,h)(C,,)3.1.1停机条件的等价性对于每个以终止状态方式停机的PDA，我们都可以构造一个等价的以空栈方式停机的PDA，反之亦然。设P1是一个空栈停机的PDA，即它的终止状态集F=。我们构造一个新的PDAP2，P2与P1基本相同，其区别在于P2比P1多两个附加的状态qf(用于描述终止状态)、qg（用于描述开始状态），一个附加的栈符号hf（用于描述初始栈符号）以及附加的转换规则。规则1(qg,,hf)=(q0,h0hf)规则2(qi,,hf)=(qf,hf)qi∈Q1由空栈PDA构造终态PDA上述附加的第一条转换规则在

8、不读入任何符号的情况下，将P1中的初始栈符号压到栈顶，并且将状态转换到P1的初始状态。然后，P2完全模拟P1进行工作，直到P1进入到空栈的情况为止。此时，P2的栈内还有一个新加入的符号hf。根据第二条附加的规则，无论P1进入什么状态qi，P2将会再进行一步状态转换(qi,,hf)=(qf,hf)，从而使P2进入到状态hf，这恰好就是P2引入的终止状态。若P1的输入符号串已空，因P1当前已是空栈，则P1接受这个输入串；