编译原理5.ppt

1、第5章自顶向下语法分析方法，5.1确定的自顶向下分析思想5.2 LL(1)语法的判别5.3部分郑智薰LL(1)语法到LL(1)语法的等变量环5.4不确定的自顶向下分析思想5.5的自顶向下分析方法，自顶向下语法分析，语法分析概念自顶向下语法分析的一般过程自顶向下语法分析面临的问题，文章分析，以及或者派生的配置过程编程语言通常通过与上下文无关的语法来说明，所以这里需要关注和解决的是上下文语法的文章分析，从语法树派生的图解表达。文章aabbaa的可能派生序列和语法树，例如：gs : SaaS asba ass sa ABA，s a s b a a b a b a，Saasaasbaasbbaaabb

2、aa saasbasabbasabbaa也就是说，始终从左到右标识输入符号字符串，首先标识符号字符串最左侧的符号，然后依次标识右侧的符号之一，直到分析结束。分析算法分类，分析方法主要从语法的起始符号开始，查找与输入符号字符串匹配的派生，或查找输入字符串最左边的派生自下而上分析方法之一。从输入符号字符串开始，从语法的开始符号，从上到下或从上到下，以所有输入字符串的所有可能方法开始语法的符号，从上到下构建输入字符串的语法树，或徐璐查找输入字符串的最左侧派生项，重复使用其他生成表达式来查找与输入字符串匹配的内容的过程。由上而下语法分析的一般程序。示例：语法G: S CAD A ABA确定输入字符串w

3、=cabd是否是语法中的句子，SSS cAdcAd a b派生过程：S cAd cAd cabd，首先选择S CAD，唯一的选择是2 .以后。w的第二个符号可以与叶节点A匹配，但第三个符号D与下一个叶节点B不匹配怎么办？看看a有没有别的选择，有！回溯，截断以A为根的子树，试验生成式(3)，可以看到吐出A识别S cAd CAD，分析过程，输入字符串w=caa的过程。1.S cAd 2 .选择(2)扩展A；可以追溯到S cAd 6。回溯到s，还有别的选择吗？不！分析失败宣言！问题，分析失败的情况，回溯后要再试。如果尝试所有回溯都没有带来成功，那就意味着分析的失败。也意味着相关字符串不能在语法中生成

4、语法。左边的递归也能带来问题左边的递归吗？像SSa一样，带来左边递归，由上而下分析语法的要求，先举个例子。(大卫亚设，美国电视电视剧)。语法GS: (1)对于SSa (2) Sb，分析baa是否语法的句子根据自上而下分析思想选择生成式(1)，将SSa语法树末尾的最左边的符号推断为非终止式。因此，如果继续按下选择(1)，语法树末尾最左边的符号仍然是非终止符。因此，选择(1)继续推导SSaSaa Saaa问题，并尝试使用S匹配输入字符串时出现。必须在不读取输入符号的情况下再次要求输入S。新的匹配原因语法包括左递归，自上而下语法分析。由上而下分析主要是确定的和不确定的两种茄子不确定的分析方法称为回溯

5、分析方法。如上所述，语法不能包含左递归确定的分析方法。语法中的更多要求，左边递归，语法GS: SSASB定义的语言可以用集合L=ban|n1对单词W=baaa表示，不是以P开头的常规左递归格式：P=* P例如，语法SAa ASb获取左边递归，删除左边递归，删除左边递归P P|郑智薰，不以P开头的牙齿语法包含直接左递归。例如，Q表示原始语法为P Q Q Q|，语法ge: e e t | t t t * f | f f f (e) | a删除左侧递归后，以下新语法ge: (1) e te (2) e te (3) e (4) t ft(删除左侧递归后的算法) 满足牙齿要求的充分条件是语法中不包含A

6、A的有害规则和不包含A的协方差计算方法说明：将语法中的所有非终止符按特定顺序排序，A1、A2、An从A1开始删除Ai的左侧生成式的直接左侧递归，然后将左侧牙齿为A1的所有规则的右侧分别替换为A2从A1开始的生成式的A1，删除左侧包含A2的生成式的直接左侧递归。 然后，将A1，A2的右侧赋值为左侧的A3，从以A1或A2开头的生成表达式中删除左侧为A3的生成表达式的直接左侧递归，从生成表达式中直接从An中删除左侧递归，将左侧为A1，A2，An-1的右侧赋值为左侧的An。使用ai-1 | 2 |取代a2 an for I :=1 to n do begin for j 3360=1 to I-1 d

7、o ai-1 | 2r | k r Ai-Ajr等规则，以移除Ai规则的直接左耳。End从简化2中得到的语法，简化，去除无用，什么生产方式无用？有关下一页的实例，请参阅以无法到达的非终止者为左的生产式等。是无用的生产食品。对于语法：S(abc|bc|c)S SabcS| QRb|b RSa|a使Q，R向左的生产方式没有用。从开始符号开始。首先添加配置的派生SxAy匹配为派生A的可选Aab替换，SxAy xaby xay匹配xa全部匹配，输入字符串指针返回A(因为当前输入者不能匹配Y和B)，为A的替换再次选择下一个生成Aa进行试验，SxAy xay输入字符串中的当前字符A匹配，指针前进到Y。同一

8、左侧生成表达式的右侧开始符号相同，因此，反向跟踪、派生的选择、要替换的最左侧非结束符号为B，并具有N个规则(为了做出正确的选择，解析器使用了哪些信息？示例：语法GS: S pA|qB A cAd|a B dB|c识别的输入字符串w=pccadd为GS的文章可预测推理过程：S pA pcAd pccAddpccadd测试成功的原因？由于几组茄子的概念和计算方法，要识别的符号字符串的终止符按顺序出现，可以唯一地指示应该选择哪个生产式，因此，为了找出要识别的符号字符串终止符出现的部分规律，需要引入几个茄子计算方法。First集，定义设置G=(VT，VN，S，P)是上下文无关的语法，对于非终止符，开始

9、符号集或第一组符号定义如下：FIRST()=a|*a，aVT，V*，确定的自上而下语法分析，如果有语法GS:如果SAp SBq aa ACA bbdb输入字符串为W=ccap，则可以检查该字符串。如何决定？此时，扫描的W的符号是C，因此，无论选择哪种生成，生成的符号字符串的第一个字符都必须是C。FIRST(Ap)=a，c，FIRST(Bq)=b，d，因此正确的选择必须是SAp的其他阶段、跳过、确定的自上而下语法分析、FIRST(Ap)和FIRST，但是如果A可以派生，则可能会有差异例如，如果GS: SaA Sd AbAS A输入字符串W=abd，衍生过程会怎么样？分析过程，第一步，选择生成的S

10、aA，因为当前扫描的符号是A。这是肯定的。未选择Sd。第二步是选择生成的AbAS，因为当前扫描的符号为B。这也是肯定的。如何选择第三步？选择AbAS会导致失败。选择a，接受abASabS，选择Sd，就可以成功。为什么？两个例子的差异，后面有空的生产表达式。选择成功原因：s的第一个字符集包含d。分析仍然是确定的。输入字符串括号，通常可以将“#”用作输入字符串的终止符，也可以将其视为输入字符串括号，例如，对于符号字符串W=abd，W=abd#，FIRST集的计算和编程实现。非终止符能否推出空FIRST集的计算方法，请参阅P80表5.1算法说明首先创建以语法中的非终止符数为上限的一维数组。数组元素是

11、非终结点，每个非终结点都有对应的标志位。牙齿值分别为“待定”、“是”和“否”非终止符能否推空算法：数组中每个扫描语法的生成式将删除右端有终止符的所有生成式。这将删除不是终结点的部分左侧的所有生成表达式，从而将阵列中不是终结点的标记更改为“否”。因为这意味着终结点不能为空(为什么？)如果非终结器的生成右侧是，则在数组中将非终结器的标志设置为“是”，并从语法中删除所有非终结器的生成(这是什么意思？)扫描生成式右侧的每个符号(1)如果要扫描的非终止式在阵列中的相应标志为“是”，则删除非终止式，如果生成式右侧为空，则将生成式左侧的非终止式在阵列中的相应标志更改为“是”，并删除非终止式左侧的所有生成式。然后，删除生成表达式，从而删除生成表达式左侧非终止符的所有相关生成表达式，将数组中非终止符的对应标志更改为“否”，然后重复步骤C，直到再次扫描语法的生成表达式。阵列的非终结点对应的标志不再更改。例如，已知语法GS: SAB SBC A AB Bad CAD CAD FIRST集的计算是关系图，其中语法符号的FIRST集，P81，根据定义，如果有一点XVT，FIRST(X)=X XVN，结果X a，aVT，则为aFIRST非终结器或指定的符号字符串可以获得FIRST集合。first (s)=a，b C FIRST(D)=a，C，结果右