文档介绍：该【自上而下语法分析47 】是由【小落意心冢】上传分享，文档一共【57】页，该文档可以免费在线阅读，需要了解更多关于【自上而下语法分析47 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。自上而下语法分析47语法分析是继词法分析之后编译过程的第2阶段。它的主要任务是对词法分析的输出结果——单词序列进行分析,识别合法的语法单位。语法分析最常用的方法有:优先方法、递归下降法、LL方法和LR方法。所谓自上而下分析是指从树的根结点开始,为给定的输入串构造一棵语法树。本章中,我们通过讨论一个一般的非确定的自上而下分析器来讨论上下无关语言的自上而下分析器的设计。(PDA)类。所谓一个下推或栈自动机(StackAutomaton),非形式地说,应包含:①一个输入符号串;②一个读头,它从左至右移动,每次读进一个输入符号;③一个有穷状态自动机,用于控制整个系统的操作;④一个后进先出下推栈,下推自动机的非空移动:,一个PDA是一个七元组: (Q,∑,H,δ,q0,Z0,F)Q是状态的有穷集,它的每个元素称为一个状态;∑是有穷的字母表,它的每个元素是一个输入符号;H是有穷的下推栈字符表,它的每个元素称为一个栈符号。q0∈Q是该PDA的初态;Z0∈H是下推栈的初始符号;F?Q是一个终态集(或接收状态集);它的每个元素称为终态;(可空)。。PDA的动作可用δ定义式来表示为:δ(q,a,z)={(p1,h1),(p2,h2)…(pn,hn)}它的含义为:在控制器当前状态为q,下推栈顶符号为z,输入符号为a的情况下,把控制器的状态改为pi,用hi替换栈顶的z,并让读头右移一格。:(q,w,h)其中,q∈Q;w∈∑*是尚待扫描的输入串,包括读头当前所指的符号;h∈H*是栈的内容。PDA的一次移动可看作是从一种构形变换成另一种构形的一种方式。反过来,构形又为定义PDA的移动提供了一种更简单的手段。我们称 (q,ax,Zh′)├(p,x,hh′) 是一次可能的移动,当且仅当(p,h)∈δ(q,a,Z)。常用├+表示由一次或多次移动组成的序列。用├*表示由零次或多次移动组成的序列。注意“零”次移动并不改变当前的构形。(M)可表示为:L(M)={ω??*︱(P0,ω,Z0)├*(P,?,?)}(空栈接收)或者L(M)={ω??*︱(P0,ω,Z0)├*(P,?,h)&p?F}(终态接收),其的两个状态分别是p和Q,δ(p,a,Z)={(p1,h1),(p2,h2),…},输入符号是0和1,栈符号是R,B和G。该PDA识别由符号0和1组成的所有回文(Palindrome)。,所构造的PDA用下面的移动序列来接收它(注意,我们可从构形中省掉状态,因为它总是相同的): (q,00c11,S)├4a(q,00c11,0S1)├1(q,0c11,S1) ├4a(q,0c11,0S11)├1(q,c11,S11) ├4b(q,c11,c11)├3(q,11,11) ├2(q,1,1)├2(q,ε,ε)(接收)