精华内容
下载资源
问答
  • 编译原理-语法分析详解

    千次阅读 多人点赞 2020-12-20 20:57:58
    一文带你读懂语法分析(编译原理)一、前言二、前置知识三、自顶向下的语法分析1、自顶向下的分析会遇到的问题a. 二义性问题b. 回溯问题c. 左递归引起的无穷推导问题2、解决以上问题a. 二义性问题 一、前言   最近...

    一、前言

      最近刚考完编译原理,抽出一点时间,来把学的知识总结一下,以便之后的回顾。在这篇博客里可能会稍作全面地讲解语法分析(学生角度),涉及到FIRST集和FOLLOW集的求取、自顶向下的语法分析和自底向上的语法分析。其中自顶向下的语法分析会包含预测分析法和递归下降法以及LL文法的介绍;自底向上的语法分析则会包含算符优先、LR(0)、SLR(1)、LR(1)和LALR(1)的介绍。内容比较多,只需要学习部分内容的话,按需目录跳转即可。

    二、前置知识

      既然大家已经准备学习语法分析,那这里我就默认大家已经了解过编译原理的一些基本概念(如:语言、文法、产生式等基础概念)和学习过编译器前端的词法分析。
      首先来看一下语法分析的概念:
      语法分析(syntax analysis)是编译程序的核心部分,其任务是检查词法分析器输出的单词序列是否是源语言中的句子,亦即是否符合源语言的语法规则。
      简单来说,语法分析就是读取词法分析产生的单词序列,看是否满足该语言的语法。比如c语言中,int double =,这种不符合语言语法规范的错误就是在语法分析中检查出来的。
      当然,语法分析远远不只有检查语句语法规范的功能,还涉及到符号表的管理、错误分析报告、为语义分析提供入口(语法制导翻译)等等。但在这里不是我们讨论的重点。
      要想判断一个句子是否所属某一语言,一般可以通过两种角度:句子的产生(推导)和句子的识别(归约)。
      产生句子的方式是从文法的开始符号开始,逐步推导出该单词序列,也称为自顶向下的语法分析;而识别句子的方式则是逐步将构成程序的单词序列归约为文法的开始符号,称为自底向上的语法分析

    三、自顶向下的语法分析

    1、自顶向下的分析会遇到的问题

      自顶向下分析实际上是一种试探性的过程,可能导致分析效率极低甚至失败。通常,在自顶向下的分析过程中会遇到二义性问题、左递归引起的无限推导和回溯问题。

    a. 二义性问题

      对于文法G,如果L(G)中存在一个具有两棵或两棵以上分析树(或最左推导)的句子(或句型),则称G是二义性的。
      如果对于一个文法G,属于L(G)的一个句子s有多个最左推导,那在对句子s进行自顶向下的语法分析过程中将会在某一步推导遇到多个可选的产生式,此时便无法确定选用哪个产生式进行推导。若想继续分析下去,就要尝试某个产生式,如果在之后的推导过程中出现问题,就要回溯到这个分叉点,重新选择另一个产生式进行尝试,直至停止或接受。
      如下图的产生式集合:
    在这里插入图片描述
      如果我们要对id+id*id进行自顶向下的语法分析,则会出现二义性问题。如:
    在这里插入图片描述
      句子id+id*id有两个最左推导,所以存在二义性问题。
      出现二义性通常是因为文法提供的信息不全,比如上面的id+id*id,常识来看乘的运算优先级要大于加,而在上面的文法中优先级是一样的,所以为了设置算符的优先级,我们可以提供更加详细语法信息。改造过的产生式集合如下:
    在这里插入图片描述
      在改造过的文法中,乘的优先级是大于加的,所以不会出现二义性问题。具体为什么乘的优先级大于加,可以参考后面的算符优先文法
      但同样,修改后的文法的产生式集合规模会大规模地增加。

    b. 回溯问题

      假设某个产生式的左部是E,则该产生式的右部称为E的候选式。如果对于非终结符E有多个候选式存在公共前缀,则自顶向下的语法分析程序便不能准确地选择产生式进行推导,只能进行试探,出现错误要回溯到上一个分支点,再选择其它的产生式进行尝试。
      对于以下产生式集合:
    在这里插入图片描述

      如果我们要对(id)进行自顶向下的语法分析,从文法的开始符号E开始推导。想要推导出句子的第一个符号(,我们有1和2两个产生式可以选择,假设我们选择2作为最先推导的产生式,得到以下推导:
    在这里插入图片描述
      推导的产生式序列是:2->4,得到了(c),第一个(可以匹配,但到id的时候匹配错误,所以要回溯到上一步推导,选择其它可选择的产生式进行尝试。
      我们可以发现,对一个句子的推导可能会产生大量的回溯,效率极低。

    c. 左递归引起的无穷推导问题

      如果对于一个文法G,存在以下情况,则称为文法G是递归的:
    在这里插入图片描述
      简单来说如果非终结符A能在有限步推导后得到A开头的句型,则称该文法是递归的。如果只通过了一步推导,称为直接左递归;如果通过了大于一步的推导,则称为间接左递归
      同上,对于以下产生式集合,进行对id+id*id的自顶向下语法分析:
    在这里插入图片描述
      我们可以发现,产生式1是左递归的,因此在分析的过程中可能会出现一直使用产生式1进行推导的情况:
    在这里插入图片描述
      这样便会出现无穷推导。

    2、解决部分问题

    a. 二义性问题

      许多文法的二义性是由于概念不清、语法变量的定义不明确导致的(比如:算符的优先级不明确、对某个非终结符定义不清等等),此时可以通过引入新的语法变量改写文法来解决。
      实际上,二义性问题没有特别形式化的解法,需要一定的经验和创造力来对文法进行改造,所以这里不对其进行详细讲解。

    b. 提取左因子

      如之前所说的,若一个非终结符有多个拥有公共前缀的候选式,对该非终结符进行推导的时候就难以选择合适的产生式进行推导,因此会产生回溯问题。这里,我们便可以使用提取左因子的方式在一定程度上规避回溯问题。
      提取左因子其实和简单数学中的提取公因式差不多。对某一非终结符A的候选式,提取它们不为ε的最大公共前缀C和公共前缀后的文法符号串S,引入新的语法变量A',并引入产生式A'->S,用A'替换掉候选式中的公共前缀后的文法符号串,使其出现这样的形式:A->CA' A'->S
      上面的解释可能过于生硬,这里我们对一下产生式集合进行提取左因子的操作:
    在这里插入图片描述

      我们可以明显地发现产生式1和2的右部存在公共前缀(,对非终结符E,如果下一个要推导出的终结符是(,我们只能对产生式1或2进行试探,出现错误后再回退选择另一个产生式进行尝试。因此我们可以提取产生式1和2右部的最大公共前缀(,然后引入新的文法变量M和新的产生式来消除产生式1和2的公共前缀。
    在这里插入图片描述
      进行完以上改造后,该产生式集合不再有某一文法变量的候选式存在公共前缀问题。对非终结符E,如果下一个要推导出的终结符是(,我们只能选择产生式1进行推导,这样就消除了公共前缀引起的回溯问题。
      需要注意的是,提取左因子并不能完全消除回溯,只能消除由公共前缀引起的回溯。这个问题我们将在后面进行讨论。

    c. 消除左递归

      我们已经知道,左递归分为直接左递归间接左递归,虽具体的消除方式不同,但思想还是一致的,那就是将左递归转换成右递归
      这里我们可以讨论下为什么转换为右递归即可消除无穷推导。实际上到底是左递归还是右递归会引起无穷推导,是与单词序列的读取方向有关。对于自顶向下的语法分析,我们默认是使用的最左推导,也就是每次关注尽量左的非终结符。所以每次推导完,关注的是推导后最左边的非终结符,而由左递归的定义可知,最左边的非终结符与产生式左部是一样的,所以一旦套起娃,便会出现无穷推导。
    在这里插入图片描述
      红框圈起来的是最左推导关注的目标非终结符。因此不难理解,对于右递归,最左推导不会出现无穷推导。
    在这里插入图片描述
      红框圈起来的是最左推导关注的目标非终结符。对右递归,即使进行推导,关注的非终结符也不会是引起无穷推导的因子。
      同样的,如果我们使用的是最右推导,那右递归便是引起无穷推导的因素,需要将其转换为左递归。
      言归正传,我们回到消除左递归的问题上。根据之前说的,我们可以将左递归转换成右递归。
    在这里插入图片描述
      这里改造看起来有点抽象,但实际上是比较容易理解的。通过分析原产生式,我们不难发现,产生的句子是这样的结构:
    在这里插入图片描述
      我们通过A'构建一个左右递归转换的桥梁,便可得到等价转换。当然,如果βε,那我们就不用大费周折进行转换,直接调转即可。
    在这里插入图片描述
      通过以上的做法便可以消除直接左递归。消除间接左递归的方法也是将左递归转换为右递归,但我们需要进行一些略微复杂的操作。
      看以下的产生式集合:
    在这里插入图片描述
      我们很容易发现A->Ac是存在直接左递归的。然而,如果将A->Sd带入S->Aa,会得到S->Sda,所以同样存在间接左递归。
      为了消除间接左递归,我们首先要为每个非终结符编号,这里我们将A编为1,S编为2,然后按编号从小到大遍历产生式左部为目标非终结符的产生式,将其产生式右部的其它非终结符通过其它产生式进行替换。如果发现存在直接左递归,就使用上面的方法进行消除,不存在的话就跳过直到遍历完成。
    在这里插入图片描述
      在进行变量代换的时候不一定要带到底,当明显发现不存在左递归之后就可以适当地停止,比如上面图片中的步骤2,对A'的替换就是适可而止的。

    3、LL(1)文法

      存在回溯问题的分析我们可以称之为不确定的自顶向下分析,而存在回溯问题的分析我们称之为确定的自顶向下分析。然而,确定的自顶向下分析不能分析全部的文法,只能分析满足一定条件的文法。LL(1)文法就是能够满足确定的自顶向下分析条件的文法。
      能够彻底消除回溯,实现确定的自顶向下分析的文法有以下要求:

    1. 无二义性
    2. 无左递归
    3. 任意一个语法变量A的各个候选式所能推导出的第一个终结符必须各不相同

      前两点在之前已经讲解过了,而通过分析不难发现提取左因子是满足第三点的一个充分条件。如果某一非终结符的候选式存在公共前缀,那很明显是不满足第三点的。
      确定的自顶向下分析首先从文法的开始符号出发,每一步推导都根据当前句型的最左非终结符A和当前输入符号a,选择A的某个候选式α(alpha)来替换A,并使得从α(alpha)推导出的第一个终结符恰好是a。但不能存在多个候选式推导出的第一个终结符是a,这样就不能确定选择哪个产生式进行推导。
      为了表示第一个终结符这个概念,我们要引入FIRST集这个概念。

    a. FIRST集的概念以及求解

      FIRST集的概念如下:
    在这里插入图片描述
      简单来说就是某个串的FIRST集就是这个串能推导出的第一个终结符的集合(该终结符必须在最左边)。
      我们可以给出以下规则:
    在这里插入图片描述
      求非终结符的FIRST集的时候主要关注产生式左部的符号和产生式右部的最左侧符号。比如我们要求A的FIRST集,先找到所有左部为A的产生式,然后遍历这些产生式的右部:如果右部第一个符号是终结符,那么把这个终结符加入到A的FIRST集中;如果右部是ε,把ε加入到A的FIRST集中;如果右部第一个符号是非终结符B,将该非终结符B的FIRST集加入A的FIRST集中,但需要注意的是,如果B的FIRST集存在ε,向FIRST(A)中添加FIRST(B)的时候就要去掉ε,然后加上下一个符号C的FIRST集,如果FIRST(C)还有ε就继续向后推演,以此类推。
      对于最后一种比较复杂的情况,我们有以下结论:
    在这里插入图片描述
      对于这种比较复杂的情况,有没有ε取决于连续的最后一个FIRST集含ε的符号是不是产生式右部的最后一个符号。因为只有产生式右部所有符号都有可能推导出ε,产生式左部的符号才能推导出ε
      需要注意的是,我们认为一个终结符的FIRST集就是它本身

    b. FOLLOW集的概念以及求解

      在LL(1)文法中,如果存在A->ε这样的产生式,就代表在推导过程中,我们可以直接利用这种空产生式消掉A。比如当前串是Aab,我们可以利用A->εA推导为空,串将变为ab
      在这种存在空产生式的情况下,仅仅利用FIRST集就明显不够了。因为对于某个要推导出的终结符a,我们可以将现在的待推导非终结符推导为空,然后利用下个符号最左推导出a(即判断下个符号的FIRST集是否包含该终结符a)。
      因此我们便要引入FOLLOW集这个概念,来记录某个非终结符后可能出现的第一个终结符。
    在这里插入图片描述
      我们可以给出以下的规则:
    在这里插入图片描述
      求FOLLOW集的时候主要关注产生式右部的符号。比如我们要求A的FOLLOW集,找到所有产生式右部为存在A的产生式,然后找A后面的第一个符号:如果A后第一个符号是终结符,那么把这个终结符加入到A的FOLLOW集中;开始符号的FOLLOW集包含##是终止符,代表一个句子的末尾,可以看做EOF,在有的材料中是$);如果A是最后一个符号,要将该产生式左部非终结符E的FOLLOW集加入A的FOLLOW集;如果A后第一个符号是非终结符B,将该非终结符B的FIRST集(要去除ε)加入A的FOLLOW集中,但需要注意的是,如果B的FIRST集存在ε,要加上下一个符号C的FIRST集(要去除ε),如果FIRST(C)还有ε就继续向后推演,以此类推,如果直到最后一个符号的FIRST集还包含ε,要将该产生式左部非终结符E的FOLLOW集加入A的FOLLOW集
      需要注意的是,我们认为终结符是没有FOLLOW集的

    c. SELECT集的概念以及求解

      引入FIRST集和FOLLOW集之后,我们便可以判断LL(1)文法的条件3(任意一个语法变量A的各个候选式所能推导出的第一个终结符必须各不相同)是否满足了。
      此时我们引入SELECT集(可选集):
    在这里插入图片描述
      如果一个文法满足对相同左部的产生式的SELECT集互不相交,那这个文法便满足任意一个语法变量A的各个候选式所能推导出的第一个终结符必须各不相同(条件3)。
      SELECT集其实也是比较好理解的,也是一个非终结符能推导出的最左终结符的集合但有对空产生式的优化

    d. 判断文法是否是LL(1)文法的步骤

      1.提取左因子;
      2.消除左递归;
      3.求解各个产生式的SELECT集,如果左部相同的产生式的SELECT集没有相交,则为LL(1)文法。

    e. 判断文法是否是LL(1)文法的例子

      这里我们们给出一个例子:
    在这里插入图片描述
      首先,我们遍历产生式,发现没有某一非终结符的候选式存在公共前缀,所以不需要提取左因子
      但我们发现产生式E->E+TT->T*F存在左递归,所以我们需要引入E'T'消除左递归
    在这里插入图片描述
      为了判断相同左部的各个产生式的SELECT集是否相交,我们要先求出各个非终结符的FIRST集:
    在这里插入图片描述
      然后便可以求各个非终结符的FOLLOW集:
    在这里插入图片描述
      然后求各个产生式的SELECT集:
    在这里插入图片描述
      然后判断相同左部的产生式的SELECT集是否相交:
    在这里插入图片描述
      发现相同左部的产生式的SELECT集不相交。此时满足了d部分中的三个条件,此时我们获得了LL(1)文法。

    4、预测分析法

    a. 预测分析法的原理

      经过上面的讲解,我们已经能够判断一个文法是否是LL(1)文法,但光有文法是无法进行语法分析的,需要相应的分析方案才行。预测分析法便是常用的自顶向下的语法分析方法。
      要实现预测分析法,我们要先了解其结构。预测分析器主要由符号栈、预测分析表和输入缓冲区组成。符号栈保存了当前推导出的句型、预测分析表定义了推导的规范、输入缓冲区保存了待推导出的符号序列。
      预测分析表可以使用二维数组表示,行标代表要进行推导的非终结符,列表代表要推导出的最左终结符,单元内的数据表示选用的产生式。Table[A][b]代表:对于非终结符A要想推导出最左终结符为b的短语,要采用Table[A][b]中的产生式进行推导。
      这里给出一个简单的预测分析表:
    在这里插入图片描述
      构造预测分析表的方法也比较简单,先将所有非终结符放在行首,将所有终结符(要带上终止符#)放在列首。然后对于产生式左部为非终结符A的产生式,如果终结符x属于该产生式的SELECT集,则Table[A][x]填上该产生式右部;如果产生式是空产生式(A->ε),则对于该产生式的SELECT集中的终结符x,Table[A][x]填上该空产生式右部(->ε)。
      该预测分析器的总控也比较简单,初始状态将开始符号S压入符号栈,将待读句子放入缓冲区。然后根据符号栈栈顶非终结符A和缓冲区最左符号a查预测分析表,如果Table[A][a]为空,则说明分析错误,该句子不符合语法规范;如果Table[A][a]有多个产生式,就说明该文法不是LL(1)文法;如果只有一个产生式,就利用该产生式进行推导,然后符号栈弹出一个符号(产生式左部),将该产生式右部逆向入栈(因为是最左推导),比较符号栈顶和缓冲区最左符号是否匹配,如果匹配,符号栈和缓冲区弹出相匹配的符号;如果不匹配,继续查预测分析表进行推导,直到结束或接受。

    b. 预测分析法的例子

    在这里插入图片描述
      这里我们扩展了上面判断是否为LL(1)文法的题目,要求给出预测分析表和对于一个句子i+i*i的分析过程。
      为了判断该文法是否为LL(1)文法,我们检查各个非终结符的候选式是否存在公共前缀(是否需要提取左因子)和是否存在左递归。发现不需要提取左因子但需要改造文法消除左递归。
      然后为了判断相同左部的产生式的SELECT集是否相交。我们先后求了各个非终结符的FIRST集、各个非终结符的FOLLOW集、各个产生式右部的FIRST集和各个产生式的SELECT集。
      最后得到了以下SELECT集,并发现我们改造后的文法是LL(1)文法:
    在这里插入图片描述
      到此为止的步骤和上面判断是否是LL(1)文法的题是一样的。之后我们便可以构造预测分析表。实际上,构造预测分析表只需要各个产生式的SELECT集。
      我们先将所有非终结符放在行首,将所有终结符(要带上终止符#)放在列首:
    在这里插入图片描述
      然后对于产生式左部为非终结符A的产生式,如果终结符x属于该产生式的SELECT集,则Table[A][x]填上该产生式右部;如果产生式是空产生式(A->ε),则对于该产生式的SELECT集中的终结符x,Table[A][x]填上该空产生式右部(->ε)。
    在这里插入图片描述
      得到了预测分析表后我们便可以对句子i+i*i进行分析了。首先我们构建分析器的初始状态:
    在这里插入图片描述
      然后开始分析并记录过程:
    在这里插入图片描述
      到此,这道题就解答完成了。

    5、递归下降法

      递归下降法是为每个非终结符设置一个处理子程序。如对非终结符A有产生式:
    在这里插入图片描述
      因此我们可以发现,处理子程序是要求可以递归的。
      现在我们有正则定义式A->aBC,我们用伪代码简单编写其处理子程序:

    procedure A:
    	begin
    		match 'a';  // 匹配终结符 a 并向后移动指针
    		call procedure B;  // 调用 B 的处理子程序
    		call procedure C;  // 调用 C 的处理子程序
    	end
    

      递归下降分析法就是通过递归调用非终结符的处理子程序来进行分析。这种方法简单、直观、可读性好并便于扩充;但同时效率低(使用递归)、处理能力有限而且难以自动生成。
      这里不再过多赘述递归下降分析法,如果之后有时间,我可能会再来补充。

    四、自底向上的语法分析

    1、自底向上的语法分析的介绍

      之前,我们讲解了自顶向下的语法分析的思想和设计思路。之前说过,只有确定的自顶向下语法分析才能彻底消灭回溯问题,带来较为高效的分析过程。然而,确定的自顶向下分析并不适用于所有的文法,所以便出现了自底向上的分析方法。
      与自顶向下的分析方法不同,自底向上的语法分析方法从输入串出发,反复利用产生式进行归约,如果最后能得到文法的开始符号,则输入串是相应文法的一个句子;否则输入串存在语法错误。
      自顶向下分语法分析一般是使用最左推导,而自底向上的语法分析是使用最左归约(最左归约是规范归约;最右推导是规范推导)。在自底向上分析过程中,寻找当前句型最左的和某个产生式的右部相匹配的子串(句柄),用该产生式的左部符号代替该子串(最左归约)。
      大家可能会对某些概念有些模糊,所以在这里进行简单的讲解。
      句型是能从一个文法的开始符号推导出的一个可以包括非终结符的子串,如TYPE VARIABLE = 5;,这是一个声明语句,TYPEVARIABLE都是非终结符;而句子是能从一个文法的开始符号推导出的一个只含终结符的子串,如int a = 5;,这是一个声明语句,只包含终结符。所以不难理解,句子一定是句型,而句型不一定是句子
      短语则是可以进行归约(但这个归约可能并不直接)的一个符号串。在语法树中的体现则是,以一个节点为树根的子树的叶子节点的顺序结合。如果这棵子树只含根叶两层节点(高度为2),则又称直接短语句柄是当前句型的最左直接短语
      不难理解的是,自底向上的语法分析的核心问题便是怎样寻找句柄,所以我们可以说,不同的自底向上语法分析方法实质上便是不同的寻找句柄的方法。
      我们常使用的自底向上的语法分析方法便是移进-归约分析法,该方法的分析程序主要包含了符号栈、输入缓冲区和分析表等,我们从输入缓冲区逐渐将单词移进到符号栈,并利用分析表在符号栈栈顶找到句柄进行归约
      在这里,我们可以将移进-归约分析法再度细分为优先法状态法,而我们对自底向上的语法分析的学习也是以此为基础展开的。

    2、优先法

    a. 优先法的介绍与思想

      优先法的基本思想是根据归约的先后次序为句型中相邻的文法符号规定优先关系,我们可以通过符号间的优先关系来确定句柄。
      比如在简单数学运算的文法中,对a+b*c进行分析。在最简单的最左归约中,我们应该先对句柄a+b进行归约。但很明显,*的优先级要大于+,所以通过终结符的优先关系我们可以得知,实际上应该先对b*c进行归约。
      然而,与确定的自顶向下的语法分析相似的是,优先法也只能对满足一定条件的文法进行分析,简单优先文法算符优先文法便是其二。
      下面简单说明下简单优先文法算符优先文法的概念:
      简单优先文法:如果各文法符号之间的优先关系互不冲突(即至多存在一种优先关系),则可识别任意句型的句柄
      算符优先文法:仅对文法中可能在句型中相邻的终结符定义优先关系,并且各终结符对之间的优先关系互不冲突。
      这里,我们对优先法的讲解只关注基于算符优先文法算符优先分析法

    b. 算符优先分析法

      算符优先分析法在分析表达式的过程中尤为有效。其思想是将文法中的终结符视为算符,借助算符之间的优先关系来决定句柄。
      我们可以如下定义算符间的优先关系:
    在这里插入图片描述
      但需要注意的是,这里的比较是涉及到方向的,可以看做矢量。比如* > ++ > *是不冲突的,前者是说左边的*优先度大于右边的+,而后者是说右侧的*优先度小于左侧的+。这里给个例子,在a*b+c中要先归约a*c,而在a+b*c中要先归约a+b。所以冲突只存在于同向中,如* > +* < +
      在表达式A+B*C中我们要确定运算顺序,只需要比较运算符的优先级和运算对象没有关系,所以这里我们引入算符文法的概念:如果文法 G 中不存在具有相邻非终结符的产生式,则称为算符文法。此时,只存在运算对象和运算符相邻,而不存在运算对象和运算对象相邻,更有利于我们确定运算顺序。
      如下图不存在相邻的非终结符,所以是算符文法
    在这里插入图片描述
      但即使满足了算符文法的条件,我们还是无法对其句子(如:id+id*id)进行有效的分析。因为算符文法本身是没有体现算符间的优先级的。所以我们要定义算符之间的优先关系。
      对于优先关系的确定,我们给定以下规则:
    在这里插入图片描述
      如果一个算符文法的任意两个算符(终结符)在同一方向上只存在一种优先关系,则称该文法为算符优先文法
      我们简单判断下以下文法是不是算符优先文法。
    在这里插入图片描述
      如果我们用产生式E->E-E替换掉E->E+E中右部第一个E,我们可以得到E->E-E+E,此时- > +;如果我们用E->E+E替换掉E->E-E中右部第二个E,我们也可以得到E->E-E+E,但此时- < +。所以对算符+*在同一方向上存在不同的优先级,所以该文法不是算符优先文法。
      回到正题,为了语法分析器的高效运行,我们需要数据结构来存贮不同算符间的优先关系。这里我们通常使用优先矩阵优先函数来记录。

    c. 获取算符间的优先级关系

      在构造优先矩阵优先函数前,我们需要先获取算符间的优先级关系。先前我们已经知道了算符优先级的规则与定义,但并不知道具体地求解方式,为了更好地求解优先级关系,我们要引入FIRSTOPLASTOP的概念。
    在这里插入图片描述
      FIRSTOP又称最左终结符集,是一个非终结符可推导出的最左终结符(不是最左的符号,是最左的终结符)集合;LASTOP又称最右终结符集,是一个非终结符可推导出的最右终结符(不是最右的符号,是最右的终结符)集合。
      下面给出FIRSTOPLASTOP的具体求法:
    在这里插入图片描述
      在这里我们不用考虑ε带来的影响,因为算符优先文法是不存在空产生式的。
      然后我们便可以通过FIRSTOPLASTOP来确定算符间的优先关系:
    在这里插入图片描述

    d. 优先矩阵的构建

      先前我们已经求得了算符之间的优先级关系,现在我们可以通过优先级关系来构建优先矩阵。
      优先矩阵是一个二维矩阵,第一行和第一列是所有的终结符(包括结束符#),Table[x][y]=op的意义是存在Table[x][0] op Table[0][y]的优先关系。
      这里给出一个例子的求解过程,对于以下算符优先文法的产生式集合,求解其优先矩阵:
    在这里插入图片描述
      首先我们要求FIRSTOPLASTOP集合:
    在这里插入图片描述
      然后遍历产生式集合,寻找优先级关系:
    在这里插入图片描述
      然后我们便可以构造优先矩阵:
    在这里插入图片描述
      #的优先关系可以通过增加语法变量S’和产生式S’->#S#来完成;当然我们也可以认为#的优先级小于其它任何算符,在上图中我们便是这样做的,这种做法虽然不是十分严谨,比如#可能和某个算符不存在优先级关系,但我们认为#的优先级更小。但这样一般不会影响求解的结果。

    e. 优先函数的构建

      我们可以发现,如果使用优先矩阵存储算符间的优先关系,会占用较大的空间,为O(n^2);所以我们可以使用优先函数来减少占用的空间资源,优先函数占用的空间为O(2n)
      优先函数的构建遵循以下规则:
    在这里插入图片描述
      在求优先函数之前,我们可以先求出优先矩阵,比较直观但相对麻烦;我们也可以求出FIRSTOP和LASTOP后直接通过优先关系画出有向图,但不直观。现在,我们对以下算符优先文法求优先函数:
    在这里插入图片描述
      这里我们省略具体的求解过程,并且先求出优先矩阵,使过程更加明显。以下是其优先矩阵:
    在这里插入图片描述
      然后通过优先矩阵构建有向图:
    在这里插入图片描述
      然后找到以每个点为起点的最长路径长度,获取优先函数:
    在这里插入图片描述
      优先函数虽然能明显降低存储算符间优先关系的空间消耗,但同时也存在一些问题。比如上题中的idid不能比较,但通过观察优先函数,f(id)=4<g(id)=5,所以优先级id<id。这是因为将偏序关系转化为了全序关系,所以原来无法比较优先级的算符变得可以比较了,这使得程序的检错能力降低,但并不一定会影响分析的进行。

    f. 利用算符优先分析方法进行语法分析

      算符优先分析方法是移进-归约分析法的一种,所以我们通过不断向符号栈移进缓冲区中的符号,并通过优先关系寻找句柄,以归约。我们一般通过<关系寻找句柄头,通过>关系寻找句柄尾。
      我们要知道的是,无论是使用优先矩阵还是优先函数优先关系,其分析过程都不会有太大变化,因为我们只是从存储结构中获取优先关系,,假设我们分析串#a#的优先关系,利用优先矩阵是通过比较Table[#][a]中的符号来比较#a的优先关系,通过比较Table[a][#]中的符号来比较a#的优先关系;利用优先函数则是通过比较f(#)g(a)的大小来比较#a的优先关系,通过比较f(a)g(#)的大小关系来比较a#的优先关系,其中值越大,优先程度越高。此时我们应该可以获得# < a > #的优先关系,此时我们可以发现a是句柄,要对其进行归约。
      这里我们给出一个例子,在以下文法的基础上对id+id进行分析:
    在这里插入图片描述
      这道题在上面已经解答过,所以这里直接沿用之前的结果,以下是优先矩阵:
    在这里插入图片描述
      分析过程如下:
    在这里插入图片描述
      到此,对id+id的分析就结束了。之前我们说的是通过<找句柄头,通过>找句柄尾,但在实际分析过程中是比较直观的,被< >括起来的便是句柄。
      但我们同时也能在分析过程中发现不少问题,比如在第六步中被< >括起来的是+,我们却对F+F进行归约;同样在第六步中,虽然待归约串是F+F,但我们却使用E->E+T进行归约,产生式右部对不上。
      总结一下就是:有时未归约真正的句柄;不是规范归约;归约的符号串有时和相应产生式的右部不同。
      出现以上的问题的原因是算符优先文法未定义非终结符之间的优先关系,不能识别由单非终结符组成的句柄;而在算符优先分析法中的句柄和我们之前所说的句柄不是一个句柄。前面说的句柄是最左直接短语,而在算符优先分析中的句柄是最左素短语最左素短语是至少含有一个终结符,而且不递归含有更小的素短语的短语。这里不再详细展开素短语的求解方法,但其实和求短语是同一种方法,找子树,只不过每求得一个短语后要对该短语进行判断,是否至少含有一个终结符,是否不含有更小的素短语,如果都满足了,那这个短语是一个素短语。

    3、状态法

    a. 状态法的介绍与思想

      在之前的讲解中我们学习了移进-归约方法中的优先法,它可以有效地进行自底向上的语法分析,但同时,它存在着诸多局限,如不能处理所有的文法,算符优先分析无法处理非终结符之间的优先关系,所以如果产生式中存在相邻的非终结符(非算符文法),将难以分析,而且终结符之间也只能有一种优先关系;存在查不到的语法错误;在发现句柄(最左素短语)尾后需要向前搜索找句柄头…所以优先法很难广泛应用在语法分析中,更多的是在表达式分析中使用。
      此时,我们便可以使用状态法进行自底向上的语法分析。该方式是使用确定的有穷状态机(DFA)来进行语法分析,通过当前状态、移进单词和目标动作推进分析。
      LR(k)分析法便是状态法的一种实现。L代表从左向右读入符号、R表示最右推导的逆过程(即规范(最左)归约)、k是归约时超前读入的字符个数以便确定使用的产生式。当k=1时便可以满足绝大多数高级语言编译程序的需要。
      LR分析解决了算符优先分析存在的诸多问题。LR的归约过程是规范归约过程;适用范围广,可识别所有上下文无关文法描述的程序设计语言;分析速度快,准确定位错误。但也存在一点小问题,便是构造分析表的过程较为复杂,所以多采用自动生成的方式(YACC)。
      为了更好地表示当前状态,我们引入项目这个概念。项目在形态上就是产生式加上一个点,而这个点代表了当前识别的程度。如A->.BC,这个项目就代表了还没有读取任何符号,BC是待读符号;而A->B.C,这个项目就代表了已经读入了BC是待读符号;而A->BC.,这个项目就代表了已经读入了BC符号,没有待读符号,可以进行归约了。
      简单来说,项目中的左边便是已经读入的符号,右边是还没有读入的符号,如果在最右边就代表已经读取完,可以进行归约了。
      首先我们先介绍一下LR分析程序的组成部分。LR分析程序由符号栈、状态栈、分析表、缓冲区、总控程序等部分构成。符号栈存储当前分析过的单词、状态栈记录当前状态、分析表记录状态与待读符号决定的动作、缓冲区保存待读符号、总控程序控制整个分析过程。
      符号栈中的符号串是当前句型的活前缀之一。活前缀是不含相应句型的句柄右部的任何符号的前缀。如果已得到待规约的句柄,该活前缀也称为可归前缀。
      所有活前缀构成一个正则语言,对文法的识别就变成利用有穷状态机对规范句型的活前缀的识别的过程。
      有穷状态自动机的状态转移函数包括两个表:动作表(action表)和转移表(goto表),两个表统称为LR分析表:
      1、 ACTION表示当前状态面临输入符号时应采取的动作;action[S,a]=m的意义是对当前状态S(状态栈栈顶状态),当前输入符号为a时进行的语法动作,该动作m包括移进(移进后进行状态的转换(shift),简写是sxs代表转换,x目标状态编号)、归约(归约是reduce,简写为rxr是reduce的简写,x是利用编号为x的产生式进行归约)、接受(acc,分析结束)和出错。
      2、GOTO表示当前状态面临文法符号(非终结符)时应转向的下一个状态。goto[S, X]=x意味着当栈顶状态为S,且分析器刚归约出语法变量X时要转向的下一个状态x
      与优先法相同的是,状态法的关键也是分析表的构建,而分析表是驱动分析的基础。LR分析法在错误检测的强度从低到高是LR(0)->SLR(1)->LR(1),而LALR(1)是对LR(1)的粗化,LR(1)是LALR(1)的细化。它们的总控程序并没有大的差异,只是在分析表的求解过程中有差异。
      总控程序的分析流程如下:
    在这里插入图片描述
      为了使过程更加直观,这里我们给出一个例子来展示总控程序的分析流程。由于我们还没有学习构建分析表的方法,所以这里直接给出对应文法的分析表。
    在这里插入图片描述
      这里我们直接给出该文法的分析表,为了使其尽量直观,err不再填入分析表,用空来替代:
    在这里插入图片描述
      以下便是分析过程:
    在这里插入图片描述
      以上便是总控程序的分析流程,可能在不同材料中,分析过程的细节会有略微不同,但分析规则和分析表的使用是相同的。而在不同的LR分析法中,除了分析表的构建不同,其它步骤都是相同的,所以在介绍不同的LR分析法的时候,只会着重介绍分析表的构建方法,总控程序的流程不再赘述。

    b. LR(0)分析法

      从上面的LR分析法的定义中我们不难理解,LR(0)中的0意味着可以归约的时候不需要超前搜索符号来确定归约使用的产生式,所以可以归约的时候就一定要归约。这句话现在可能不好理解,但看完下面的就很容易理解。
      我们知道,LR分析法是使用确定的有穷状态机(DFA)来构造分析表。所以我们有必要了解一下该DFA的组成。
      之前我们引出了项目的概念,在LR(0)分析法的DFA中,我们要使用到LR(0)项目LR(0)项目的结构和之前说的项目结构是一样的,由产生式和点组成,点左边是识别过的符号,右边是待识别的符号。
      由数个项目组成的集合称为项目集,而项目集便是DFA中的状态。我们称DFA中所有状态的集合为项目集规范簇
      下面是一个DFA的示意图:
    在这里插入图片描述
      了解了LR(0)的DFA的基本概念后,我们就可以对产生式集合求DFA了。这里我们引入闭包的概念。
      现有一个状态中存在项目S->.AB且存在产生式A->ab。该项目点后的第一个符号是A,也就是等待归约出A,而又存在A->ab,也就是ab可以归约出A。我们转化下思维,可以通过等待移进ab,然后用ab归约出A的方式得到A。所以我们要加入新的项目A->.ab
      如此描述可能并不好理解,所以这里直接给出闭包的求取方式:
    在这里插入图片描述
      我们将这个求闭包的函数设为CLOSURE(C)
      DFA包括了一系列的状态和它们之间的转换关系,所以我们需要定义一个获取后继状态的函数GO(C, X),返回项目集(状态)C在识别到符号X后转入的新状态。
      这里直接给出GO(C, X)的规则:
    在这里插入图片描述
      此时我们便得到了状态转换的方法。得到一个DFA的必要条件是确定一个初始状态和已知获取新状态的方法,此时我们已经满足了后者,现在只要确定DFA的初始状态便可以得到该DFA。
      为了使文法有唯一出口,我们要引进拓广文法这一概念。对文法G=(V, T, P, S),添加新的开始符号S',并将产生式S'->S加入产生式集合得到新的产生式集合P',文法G'=(V, T, P', S')便是G的拓广文法。通过构造拓广文法,我们可以使文法有唯一的出口(接受点),也就是在分析表中只有一个单元是acc,可以使分析更加稳定直观。
      而DFA的初始状态I0便是拓广文法新加的产生式S'->S所产生的项目S'->.S的闭包。也就是CLOSURE({S'->.S})
      现在我们已经满足求DFA的条件了,接下来给出其具体过程。需要注意的是,我们可以通过项目集规范簇和GO(C, X)函数来体现DFA,项目集规范簇记录所有的状态,通过GO(C, X)来获取状态间的关系。
    在这里插入图片描述
      此时我们便获取了DFA,可以构建分析表了:
    在这里插入图片描述
      以上是LR(0)分析表生成程序的流程,当我们比着状态转换图填表的时候更为简单。我们先初始化分析表,即上面步骤的1,然后如果有从状态Ix到状态Iy的连线,线上标着M。如果M是终结符,则action[x][M]=sy;如果M是非终结符,则goto[x][M]=y;如果状态Iz中有项目S'->S.,则action[z][#]=acc
      得到分析表后,便可以通过a部分中的总控程序来对句子进行语法分析了。
      下面给出一个球LR(0)分析表的例子:
    在这里插入图片描述
      首先获得其拓广文法:
    在这里插入图片描述
      然后画出其DFA:
    在这里插入图片描述
      最后根据DFA获取LR(0)分析表:
    在这里插入图片描述
      然而LR(0)分析法不能分析所有的文法。因为LR(0)在可以归约的时候并不会前瞻任何符号来确定归约使用的产生式,所以当一个状态存在可以归约的项目(点在最右边)的时候,一定会归约。这就导致了这个状态在分析表action部分中对应的一行全是rx,意思就是无论下一个要读取的符号是什么,我都要先归约,也就是这部分最开始所说的可以归约的时候就一定要归约。这样的性质会导致移进-归约冲突归约-归约冲突,前者表示当一个状态中存在待归约项目和待移进项目的时候无法选择是进行归约还是进行移进,后者表示当一个状态中存在多个待归约项目无法确定先归约哪个。当一个文法的DFA中的每一个状态都不存在移进-归约冲突归约-归约冲突,那这个文法便是LR(0)文法。
      假设一个文法的DFA中的某个状态如下:
    在这里插入图片描述
      后两个项目存在归约-归约冲突,而第一个项目和后两个项目存在移进-归约冲突。此时LR(0)分析法就不足以支持分析该文法,我们需要使用检错能力更高的SLR(1)文法来进行分析。

    c. SLR(1)分析法

      SLR(1)分析法是对LR(0)分析法的优化,同时也是LR(1)分析法的简化,在可以进行归约的时候会前瞻一个符号来判断是否进行归约或选择哪个产生式进行归约。
      SLR(1)分析法构建DFA的方法和LR(0)分析法一模一样,只是在构建分析表的时候略有差别。SLR(1)分析法在某个状态存在项目A->ab.的时候,只有待读符号属于FOLLOW(A)的时候,才用产生式A->ab进行归约
      其实原理也比较简单,假设当前串是ab.cd,目前的状态中存在项目A->ab.,待读符号是c,如果c不在A的FOLLOW集中,那在该文法能产生的所有句型中,c就不可能出现在A的后面,就算我们使用产生式A->ab进行归约得到A.cd,最终也只会得到一个错误报告。所以我们已经可以预测到用这个产生式进行归约是一定行不通的,那我们为什么还要进行无谓的尝试呢,将这个机会让给其它的待归约项目或待移进项目不是更好吗?这便是SLR(1)的思想,缩小了可归约的范围。
      在整个流程中,只有构建分析表的过程SLR(1)与LR(0)稍有不同,而在只存在于有待归约项目的情况下:
    在这里插入图片描述
      只有划红线的地方与LR(0)有区别。所以在SLR(1)的构建分析表前,我们要求所有非终结符的FOLLOW集。
      下面给出一个例题:
    在这里插入图片描述
      首先求文法G的拓广文法,其产生式集合编码过后如下:
    在这里插入图片描述
      然后求每个非终结符的FOLLOW集:
    在这里插入图片描述
      之后画出DFA:
    在这里插入图片描述
      可以发现在状态I1I2I9中存在移进-归约冲突,所以在构建分析表的时候要格外注意:
    在这里插入图片描述
      此时SLR(1)分析表的构建就完成了。SLR(1)分析法已经可以满足分析部分高级语言的语法规则了,但仍然不能满足所有的文法。如对以下产生式集合构建DFA:
    在这里插入图片描述
      可以得到:
    在这里插入图片描述
      我们可以发现状态I2=属于R的FOLLOW集,所以存在移进-归约冲突。原因是SLR(1)分析法在归约的时候没有关注当前的语境。就像上图中的状态I2,判断是否要用R->L进行归约的时候,虽然=属于R的FOLLOW集,但在当前语境(上下文)中,=是不可能出现在R的后面的。这种矛盾在该文法中并不明显。我们通过其它的例子来进行展示。
      假设我们定义以下的语法规则:

    // 有如下的判断语句
    if (a < b) :
    	xxx;
    
    // 有如下的循环语句
    while (a < b) {
    	xxx;
    }
    

      此时我们可以如下简单定义该部分的产生式:
    在这里插入图片描述
      其中1是判断语句的产生式,2是循环语句的产生式,语法变量C代表判断表达式(如a<b)。现在我们不拘泥于这部分产生式的正确与否,单独考虑以下这段代码的语法分析:

    if (a < b):
    	S
    

      代码中判断体中的代码块我们直接用语法变量S表示。假设分析到了IC.:S这个程度,当前语境是判断语句,虽然{属于C的FOLLOW集,但很明显,在当前语境下{是不可能出现在C的后面的,只有在循环语句的语境下{才可能出现在C的后面,而在判断语句的语境下只有:可能出现在C的后面。实际上,FOLLOW集仅仅是针对文法来定义的,对于某个语境来说,某一非终结符后可能出现的终结符集合只能是该非终结符的FOLLOW集的子集。而正是因为SLR(1)分析法没有考虑当前语境,只通过FOLLOW集来判断是否归约,所以会出现这样的问题。为了使归约的范围再度缩小,我们可以使用考虑当前语境(上下文)的LR(1)分析法

    d. LR(1)分析法

      先前我们说过LR(1)分析法是考虑当前所在语境的分析法,所以为了在状态中导入当前语境,我们需要改变项目的结构,改变后的项目我们称之为LR(1)项目
      LR(1)项目LR(0)项目的基础上添加了展望符集合展望符集合包含了可能出现在项目左部非终结符后的终结符集合。正是通过展望符集合来体现当前语境。需要注意的是,展望符集合只在归约的时候发挥作用,在移进等其它情况下没有一点作用
    在这里插入图片描述
      需要注意的是,展望符集合一定是当前项目左部非终结符的FOLLOW集的子集
      在LR(1)项目的作用下,LR(1)分析法构建DFA的方式也会有变化。比如对于初始状态中求闭包前的初始项目S'->.S,我们需要更新为S'->.S , #,因为S'后只可能出现#
      求闭包的方法也略有改变:
    在这里插入图片描述
      也就是在产生新的项目的时候要计算可能出现在项目左部非终结符后的终结符集合。而上面δ属于FIRST(βχ)是因为β有可能是空。
      对应的,获取新状态的方法GO(C, X)也有所改变:
    在这里插入图片描述
      但项目集规范簇的求法几乎没有改变。
    在这里插入图片描述
      而之前说过,在构造分析表的方法上LR(0)、SLR(1)和LR(1)三种方法只在规约时略有不同,而在LR(1)分析法中,对可以归约的项目,只有对待读符号是该项目展望符集合中的终结符才使用该项目对应的产生式进行归约。
    在这里插入图片描述
      这里对c部分中使用SLR(1)分析法出现冲突的文法使用LR(1)文法构建DFA:
    在这里插入图片描述
      得到的DFA如下:
    在这里插入图片描述
      到此LR(1)分析法也就讲完了。虽然LR(1)分析法考虑当前语境,能将归约的范围缩到最小,有最强的检错能力,但相应的会付出相当的代价。对于一个文法,若SLR(1)的项目集规范簇有100个状态,对于LR(1)的项目集规范簇可能会有1000个状态,大大提高了分析表的状态,增大了YACC自动生成分析表的开销和分析的开销。为了尽可能降低分析表的规模,我们可以使用LALR(1)分析法

    e. LALR(1)分析法

      LR(1)分析法产生的DFA状态比较多,我们可以通过合并一些可以合并的状态来降低分析表的规模。在这里我们选择合并同心闭包
      同心闭包是具有相同的LR(0)项目的LR(1)项目闭包。它们在结构上只有展望符集合不同。
      我们可以合并那些不会带来冲突的同心的LR(1)闭包并重构分析表。
      对于具体的例子这里暂时鸽一下,之后有时间的话再更新,大家可以去别的资料查找一下。

    五、总结

      在本篇博客中主要讲解了编译原理中的语法分析,由于最近事情比较多,所以对于一些部分可能讲解得不是很细致(比如LALR(1)分析),但在总体的讲解结构上应该是没有问题的,对于讲解不细致的地方大家可以自行查询或告诉我再补充。最后希望大家能有所收获,谢谢观看!

    展开全文
  • 语法分析 分析树、 二义性(表达式文法的重写)

    一、语法分析

    1.语法分析器的任务

    记号流--------->语法分析器-------->语法树

    语法树的构建

    if (x>5)
    	y="hello";
    else
    	z=1;
    

    语法树
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210425102209645.png

    2.语法分析–上下文无关文法

    上下文无关文法是描述程序语言语法的强有力的数学工具

    乔姆斯基文法体系

    3型文法:正则文法:词法结构
    2型文法:上下文无关文法:语法结构
    1型文法:上下文有关文法
    0型文法:任意文法
    每一个外部文法(大圈)都比内部文法(小圈)表达能力强

    举个自然语言处理的例子
    自然语言中的句子的典型结构
    主语 谓语 宾语
    名词 动词 名词
    例子:
    名词:{羊, 老虎, 草, 水}
    动词:{吃, 喝}
    句子:
    羊 吃 草
    羊 喝 水
    老虎 吃 老虎
    草 吃 老虎

    对这个例子,我们进行形式化分析:

    (S表示句子,->表示推出,N表示名词,V表示动词)

    S -> N V N 
    N -> s(sheep) | t(tiger) | g(grass) | w(water)
    V -> e(eat) | d(drink)
    

    我们将其中的大写符号叫做非终结符:{S, N, V}
    将小写的符号(单个字符或连续字符或+ 、*等)(名词+谓词)叫做终结符:{s, t, g, w, e, d}
    开始符号是:S
    上下文无关文法
    上下文无关文法 G 是一个四元组:

    在这里插入图片描述
    对于之前给出的上下文无关文法的例子

    S -> N V N 
    N -> s | t | g | w
    V -> e | d
    

    在这里插入图片描述

    最左推导和最右推导

    最左推导:每次总是选择最左侧的符号进行替换
    即对于上例中的 N V N ,首先替换最左边的 N, 再替换之后最左侧的非终结符 V, 最后替换最有一个非终结符 N
    最右推导:每次总是选择最右侧的符号进行替换
    原文链接:https://blog.csdn.net/qq_37236745/article/details/83540187

    3.分析树和二义性

    分析树

    • 推导可以表达成树状结构
      和推导所用的顺序无关(最左、最有、其他)

    • 特点:
      树中的每个内部节点代表非终结符
      每个叶子节点代表终结符
      每一步推导代表如何从双亲节点生成他的直接孩子节点

      为了更好的表示,看一下这个例子

    E -> num
       | id
       | E + E
       | E * E
       推导出3+4*5的这个句子
    E -> E + E 《最左推导 》
      -> 3 + E
      -> 3 + E * E
      -> 3 + 4 * E
      -> 3 + 4 * 5
         
    

    在这里插入图片描述

    分析树的含义取决于树的后序遍历

    二义性文法

    • 给定文法G,如果存在句子s,他有两颗不同的分析树,那么称G为二义性文法
    • 从编译器的家督,二义性文法存在的问题:
      同一个程序会有不同的含义
      因此程序运行的结果不唯一
    • 解决方案: == 文法的重写==

    表达式文法的重写

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 文章目录1 实验目的和内容1.1 实验...词法分析+语法分析6.1 将实验一的词法分析作为函数写入语法分析程序6.2 调试数据6.3 调试结果7 实验调试情况及体会7.1 实验调试情况7.2 实验体会 1 实验目的和内容 1.1 实验目的

    1 实验目的和内容

    1.1 实验目的

    (1)给出 PL/0 文法规范,要求编写 PL/0 语言的语法分析程序。

    (2)通过设计、编制、调试一个典型的自下而上语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析方法。

    (3)选择最有代表性的语法分析方法,如算符优先分析法、LR 分析法;或者调研语法分析器的自动生成工具 YACC 的功能与工作原理,使用YACC 生成一个自底向上的语法分析器。

    1.2 实验内容

    (1)已给 PL/0 语言文法,构造表达式部分的语法分析器。

    (2)分析对象〈算术表达式〉的 BNF 定义如下:

    <表达式> ::= [+|-]<项>{<加法运算符> <项>}

    <项> ::= <因子>{<乘法运算符> <因子>}

    <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’

    <加法运算符> ::= +|-

    <乘法运算符> ::= *|/

    <关系运算符> ::= =|#|<|<=|>|>=

    1.3 实验要求

    (1)将实验一“词法分析”的输出结果,作为表达式语法分析器的输入,进行语法解析,对于语法正确的表达式,报告“语法正确”;对于语法错误的表达式,报告“语法错误”, 指出错误原因。

    (2)把语法分析器设计成一个独立一遍的过程。

    (3)采用算符优先分析法或者 LR 分析法实现语法分析;或者调研语法分析器的自动生成工具 YACC 的功能与工作原理,使用 YACC 生成一个自底向上的语法分析器。

    2 设计思想

    2.1 根据BNF描述该文法

    (1)对BNF中的各对象简称如下

    E:表达式

    T:项

    F:因子

    i:ident

    n:number

    (2)文法如下

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uZrnJB24-1634780701627)(C:\Users\User\AppData\Roaming\Typora\typora-user-images\image-20211021093224575.png)]

    2.2 根据文法写出LR(0)项目集规范族

    项目集规范族如下所示,一共有16个状态。

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    2.3 根据项目集规范族画出识别活前缀的DFA

    活前缀是指规范句型的一个前缀,这种前缀不含句柄之后的任何符号。在上面的项目集中一共有四种项目,分别是归约项目、接受项目、移进项目和待约项目,根据以下两条规则来构造识别文法所以活前缀的DFA。

    (1)若状态i为X->X1…Xi-1Xi…Xn,状态j为X->X1…Xi-1XiXi+1…Xn,则从状态i画一条标志为Xi的有向边到状态j;

    (2)若状态i为X->α.Aβ,A为非终结符,则从状态i画一条ε边到所有状态A->.γ。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AWuHuADb-1634780658940)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsF520.tmp.png)]

    图1 识别活前缀的DFA

    2.4 判断该文法是否是LR(0)文法

    (1)对于I1,Follow(S)={#},与+、-不冲突;

    (2)对于I2,Follow(E)={+,-,),#},与*、/不冲突;

    (3)对于I12,Follow(E)={+,-,),#},与*、/不冲突。

    综上,该文法不存在移进归约冲突,所以是LR(0)文法。

    2.5 构造LR(0)分析表

    状态ActionActionActionActionActionActionActionActionActionGotoGotoGoto
    状态+-*/()in#ETF
    0S4S5S6123
    1S7S8acc
    2r1r2S9S10r1r1
    3r4r4r4r4r4r4
    4S4S5S61123
    5r8r8r8r8r8r8
    6r9r9r9r9r9r9
    7r4r5r6123
    8r4r5r6133
    9r4r5r614
    10r4r5r615
    11S7S8S16
    12r2r2S9S10r2r2
    13r3r3S9S10r3r3
    14r5r5r5r5r5r5
    15r6r6r6r6r6r6
    16r7r7r7r7r7r7

    3 算法流程

    语法分析程序的输入是一个个单词符号的二元组,输出是一个个语法单位,它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。

    首先逐行扫描单词符号二元组,然后遍历串的每一个字符,判断是否匹配结果,再进行下一步的判断,选择对比分析表,进行归约,把对应的字母和状态压入栈中,并输出相应的语句。如果不符合这几种情况,将会归入出错处理。完整算法流程如下图所示。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jiRJPqbD-1634780658943)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsF530.tmp.jpg)]

    图2 算法流程图

    4 源程序

    #include<bits/stdc++.h>
    using namespace std;
    
    //构造结构体---二元组
    struct Two_tuples
    {
      string type;//词法分析的类型
      string value;//词法分析的值
    };
    
    string input;//全局变量定义输入
    Two_tuples result[200];//存放词法分析二元组
    int k = 0;//输入二元组时访问下标
    bool ans = true;//存放判断结果
    int fh[101],zt[101];//符号栈,状态栈
    
    bool target_judge(string input , string str) //判断是否和目标串匹配
    {
      //首先匹配长度,看长度是否一致
      if(input.length()!=str.length()) return false;
      //长度一致,逐个匹配字符
      else
      {
        for(unsigned int i=0;i<str.length();i++)
        {
          if(input[i]!=str[i]) return false;
        }
        return true;
      }
    } 
    
    void input_cf() //输入词法分析的二元组
    {
      string str;
      while(cin>>str)
      {
        //定义指针访问
        const char *d = "(),";
        char *p;
        //临时存放字符串,便于分割处理
        char buf[101];
        strcpy(buf,str.c_str()); //字符串转成数组
        //开始处理每个二元组
        p = strtok(buf,d);
        int i = 0;
        //把输入的二元组存储到结构体中
        while(p)
        {
          if(i%2==0) result[k].type = p;
          else result[k].value = p;
          i++;
          p = strtok(NULL,d);
        }
        k++;
      }
      result[k].type = "#";
    }
     
    
    //在LR分析表中判断是哪个目标串(0--8)
    int chart(string str)
    {
      if(target_judge("plus",str)) return 0;
      else if(target_judge("minus",str)) return 1;
      else if(target_judge("times",str)) return 2;
      else if(target_judge("slash",str)) return 3;
      else if(target_judge("lparen",str)) return 4;
      else if(target_judge("rparen",str)) return 5;
      else if(target_judge("ident",str)) return 6;
      else if(target_judge("number",str)) return 7;
      else if(target_judge("#",str)) return 8;
      else return -1;
    } 
    
    //ETF归约(9--11)
    int gy_1(int num)
    {
      //E---表达式
      if(num - 100 == 1) return 9;
      else if(num - 100 == 2) return 9;
      else if(num - 100 == 3) return 9;
      //T---项
      else if(num - 100 == 4) return 10;
      else if(num - 100 == 5) return 10;
      else if(num - 100 == 6) return 10;
      //F---因子
      else if(num - 100 == 7) return 11;
      else if(num - 100 == 8) return 11;
      else if(num - 100 == 9) return 11; 
      else return -1;
    } 
    
    //gy_1中规约后约几项
    int gy_2(int num)
    {
      //E---表达式
      if(num - 100 == 1) return 1;
      else if(num - 100 == 2) return 3;
      else if(num - 100 == 3) return 3;
      //T---项
      else if(num - 100 == 4) return 1;
      else if(num - 100 == 5) return 3;
      else if(num - 100 == 6) return 3;
      //F---因子
      else if(num - 100 == 7) return 3;
      else if(num - 100 == 8) return 1;
      else if(num - 100 == 9) return 1; 
      else return -1;
    } 
    
    int main()
    {
      input_cf(); //输入词法分析结果
      //LR分析表,其中大于100为归,小于100为移进
      int LR_chart[17][12]={{0,0,0,0,4,0,5,6,0,1,2,3},
                            {7,8,0,0,0,0,0,0,100,0,0,0},
                            {101,101,9,10,0,1,0,0,101,0,0,0},
                            {104,104,104,104,0,104,0,0,104,0,0,0},
                            {0,0,0,0,4,0,5,6,0,11,2,3},
                            {108,108,108,108,0,108,0,0,108,0,0,0},
                            {109,109,109,109,0,109,0,0,109,0,0,0},
                            {0,0,0,0,4,0,5,6,0,0,12,3},
                            {0,0,0,0,4,0,5,6,0,0,13,3},
                            {0,0,0,0,4,0,5,6,0,0,0,14},
                            {0,0,0,0,4,0,5,6,0,0,0,15},
                            {7,8,0,0,0,16,0,0,0,0,0,0},
                            {102,102,9,10,0,102,0,0,102,0,0,0},
                            {103,103,9,10,0,103,0,0,103,0,0,0},
                            {105,105,105,105,0,105,0,0,105,0,0,0},
                            {106,106,106,106,0,106,0,0,106,0,0,0},
                            {107,107,107,107,0,107,0,0,107,0,0,0}}; 
      int i = 0 , j = 0; //访问栈下标
      fh[0] = 8 , zt[0] = 0;//初值
      while(LR_chart[zt[j]][chart(result[i].type)]!=100)
      {
        //判断错误
        if(LR_chart[zt[j]][chart(result[i].type)]==0)
        {
          ans = false;
          break;
        }
        //移进
        else if(LR_chart[zt[j]][chart(result[i].type)]<100)
        {
          j++;
          zt[j] = LR_chart[zt[j-1]][chart(result[i].type)];
          fh[j] = chart(result[i].type);
          i++;
        }
        //归约
        else
        {
          int res = LR_chart[zt[j]][chart(result[i].type)];
          j -= gy_2(res);
          j++;
          //移入符号栈,状态栈
          fh[j] = gy_1(res);
          zt[j] = LR_chart[zt[j-1]][gy_1(res)];
          //判断错误
          if(zt[j]==0)
          {
            ans = false;
            break;
          }
        }
      }
      if(ans == true) cout<<"Yes,it is correct."<<endl;
      else cout<<"No,it is wrong."<<endl;
      return 0;
    }
    

    5 调试数据

    (1)测试样例如下

    【样例输入】
    (lparen,()
    (ident,a)
    (plus,+)
    (number,15)
    (rparen,))
    (times,*)
    (ident,b)
    
    【样例输出】
    Yes,it is correct.
    

    (2)测试样例结果如下

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4pvqlrfw-1634780658947)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsF551.tmp.png)]

    图3 样例测试结果

    6 思考:词法分析+语法分析

    6.1 将实验一的词法分析作为函数写入语法分析程序

    int main()
    {
      string st1r;
      //输入源程序
      for(int i=0;i<L-1;i++)
      {
        cin>>str1;
        //检测输入的结束
        string str;
        str = fun_cifa(str1);//调用词法分析子程序
    }
    input_cf(); //处理词法分析结果
      //LR分析表,其中大于100为归,小于100为移进
      int LR_chart[17][12]={{0,0,0,0,4,0,5,6,0,1,2,3},
                            {7,8,0,0,0,0,0,0,100,0,0,0},
                            {101,101,9,10,0,1,0,0,101,0,0,0},
                            {104,104,104,104,0,104,0,0,104,0,0,0},
                            {0,0,0,0,4,0,5,6,0,11,2,3},
                            {108,108,108,108,0,108,0,0,108,0,0,0},
                            {109,109,109,109,0,109,0,0,109,0,0,0},
                            {0,0,0,0,4,0,5,6,0,0,12,3},
                            {0,0,0,0,4,0,5,6,0,0,13,3},
                            {0,0,0,0,4,0,5,6,0,0,0,14},
                            {0,0,0,0,4,0,5,6,0,0,0,15},
                            {7,8,0,0,0,16,0,0,0,0,0,0},
                            {102,102,9,10,0,102,0,0,102,0,0,0},
                            {103,103,9,10,0,103,0,0,103,0,0,0},
                            {105,105,105,105,0,105,0,0,105,0,0,0},
                            {106,106,106,106,0,106,0,0,106,0,0,0},
                            {107,107,107,107,0,107,0,0,107,0,0,0}}; 
      int i = 0 , j = 0; //访问栈下标
      fh[0] = 8 , zt[0] = 0;//初值
      while(LR_chart[zt[j]][chart(result[i].type)]!=100)
      {
        //判断错误
        if(LR_chart[zt[j]][chart(result[i].type)]==0)
        {
          ans = false;
          break;
        }
        //移进
        else if(LR_chart[zt[j]][chart(result[i].type)]<100)
        {
          j++;
          zt[j] = LR_chart[zt[j-1]][chart(result[i].type)];
          fh[j] = chart(result[i].type);
          i++;
        }
        //归约
        else
        {
          int res = LR_chart[zt[j]][chart(result[i].type)];
          j -= gy_2(res);
          j++;
          //移入符号栈,状态栈
          fh[j] = gy_1(res);
          zt[j] = LR_chart[zt[j-1]][gy_1(res)];
          //判断错误
          if(zt[j]==0)
          {
            ans = false;
            break;
          }
        }
      }
      if(ans == true) cout<<"Yes,it is correct."<<endl;
      else cout<<"No,it is wrong."<<endl;
      return 0;
    }
    

    6.2 调试数据

    【样例输入】
    (a+15)*b 
    
    【样例输出】
    (lparen,()
    (ident,a)
    (plus,+)
    (number,15)
    (rparen,))
    (times,*)
    (ident,b)
    Yes,it is correct.
    

    6.3 调试结果

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xqRp6dLK-1634780658951)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsF571.tmp.png)]

    图4 样例测试结果

    7 实验调试情况及体会

    7.1 实验调试情况

    由上两步中的测试样例可以得到,所有的测试样例均得到了相应的输出结果,说明代码编写成功,并且在代码中设置了出错处理,以便解决其他情况。

    本次实验同时也实现了词法分析与语法分析合在一起去识别源程序的程序,但依然存在一些问题,比如语句只能一句一句地去识别,而不能进行整体识别,该问题会在后续过程中加以解决。

    7.2 实验体会

    这次实验采用的方法是自下而上分析中的LR分析法,在做实验之前,一直考虑是用算符优先分析还是LR分析来写,最后还是决定用LR分析来写。LR分析算法比较难算的地方是构造LR分析表,需要首先画出项目集规范族和DFA,需要注意的是要认真写出每个项目集规范族,以防错了一个会影响整个结果。再三检查后,才要开始按照规则构造ACTION和GOTO 分析表。分析表也需要多次核实,如果写错一个,在归约过程中就会出错。

    在写代码的时候,由于归约和移进是通过s和r进行区分,于是我想到如果归约的话就加100,而acc就用100来表示,减少判断,给编码带来了方便。在判断结束之前,只有两个动作分别为移进和规约,然后分别对这两个过程进行处理就可以。

    因为自己完成代码比较早,在当时上实验课时老师说道分析表是不是可以用代码来构造,算符分析表构造可能相对容易,但LR分析表中构造DFA就比较麻烦,根据DFA构造分析表的过程不算困难。

    通过这次的实验,自己回顾了算符分析和LR分析的具体方法,也计算了老师ppt里的几道练习题,对于自下而上的语法分析过程进一步的理解也通过这次实验加强了自己处理字符串和运用栈来解决问题的能力。对编译原理的语法分析过程有了更好的理解,为下一次语义分析奠定基础。

    最后,感谢刘善梅老师和其他同学在这次实验中给予我的帮助,不胜感激!

    展开全文
  • 文章目录1 实验目的和内容1.1 实验目的1.2 实验内容1.3 实验要求2 设计思想2.1 根据BNF描述该文法2.2 根据文法画相应的语法图2.3 判断是否是LL(1)文法---求First、Follow集2.4 递归下降子程序3 算法流程4 源程序5 ...

    1 实验目的和内容

    1.1 实验目的

    (1)给出 PL/0 文法规范,要求编写 PL/0 语言的语法分析程序。

    (2)通过设计、编制、调试一个典型的自上而下语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步 掌握常用的语法分析方法。

    (3)选择最有代表性的语法分析方法,如递归下降分析法、预测分析法; 选择对各种常见程序语言都具备的语法结构,如赋值语句,特别是表达式,作为分析对象。

    1.2 实验内容

    (1)已给 PL/0 语言文法,构造表达式部分的语法分析器。

    (2)分析对象〈算术表达式〉的 BNF 定义如下:

    <表达式> ::= [+|-]<项>{<加法运算符> <项>}

    <项> ::= <因子>{<乘法运算符> <因子>}

    <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’

    <加法运算符> ::= +|-

    <乘法运算符> ::= *|/

    <关系运算符> ::= =|#|<|<=|>|>=

    1.3 实验要求

    (1)将实验一“词法分析”的输出结果,作为表达式语法分析器的输入,

    进行语法解析,对于语法正确的表达式,报告“语法正确”;对于语

    法错误的表达式,报告“语法错误”, 指出错误原因。

    (2)把语法分析器设计成一个独立一遍的过程。

    (3)采用递归下降分析法或者采用预测分析法实现语法分析。

    2 设计思想

    2.1 根据BNF描述该文法

    (1)对BNF中的各对象简称如下

    B:表达式 C:乘法运算符

    J:加法运算符 N:无符号整数

    X:项 S:标识符

    Y:因子 G:关系运算符

    (2)文法如下

    B->JX(JX)|X(JX)

    X->Y(CY)*

    Y->S|N|(B)

    J->+|-

    C->*|/

    G->=|#|<|<=|>|>=

    2.2 根据文法画相应的语法图

    (1)表达式

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-E4Eno25n-1634695547322)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEAD.tmp.jpg)]

    图1 表达式—语法图

    (2)项

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rAdwgE3F-1634695547328)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEAE.tmp.jpg)]

    图2 项—语法图

    (3)因子

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JuUz14zj-1634695547333)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEAF.tmp.jpg)]

    图3 因子—语法图

    2.3 判断是否是LL(1)文法—求First、Follow集

    (1)改文法没有左递归。

    (2)各非终结符的First、Follow集如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1Vo8F67r-1634695547338)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEB0.tmp.jpg)]

    (3)根据LL(1)文法的判断规则可知,该文法满足LL(1)文法的条件,所以该文法是LL(1)文法。

    2.4 递归下降子程序

    (1)表达式

    PROCEDUER B;
    BEGIN
      IF SYM = '+' OR SYM = '-' THEN ADVANCE;
      ELSE IF SYM 在 First(X) THEN
      BEGIN
        ADVANCE;
        X;
      END
      ELSE ERROR; 
      WHILE SYM = '+' OR SYM = '-' THEN
      BEGIN
        ADVANCE;
        X;
      END
    END
    

    (2)项

    PROCEDUER X;
    BEGIN
      IF SYM 在 First(Y) THEN
      BEGIN
        ADVANCE;
        Y;
      END
      ELSE ERROR; 
      WHILE SYM = '*' OR SYM = '/' THEN ADVANCE;
      IF SYM 在 First(Y) THEN
      BEGIN 
        ADVANCE;
        Y;
      END
      ELSE ERROR;
    END
    

    (3)因子

    PROCEDUER Y;
    BEGIN
      IF SYM = '(' THEN
      BEGIN
        ADVANCE;
        B;
        ADVANCE;
        IF SYM = ')' THEN ADVANCE;
        ELSE ERROR;
      END
      ELSE IF SYM 在 First(Y) THEN ADVANCE;
      ELSE ERROR;
    END
    

    3 算法流程

    语法分析程序的输入是一个个单词符号的二元组,输出是一个个语法单位,它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。

    首先逐行扫描单词符号二元组,然后遍历串的每一个字符,判断字符是不是+或-、*或/、因子的first集,再进行下一步的判断,选择进行表达式分析、项分析和因子分析,并输出相应的语句。如果不符合这几种情况,将会归入出错处理。完整算法流程如下图所示。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hNx9tFQu-1634695547341)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEC0.tmp.jpg)]

    图4 算法流程图

    4 源程序

    #include<iostream>
    #include<string>
    #include<stdlib.h>
    using namespace std; 
    
    #define L 8 
    
    void fac_aly();
    void all_aly();
    
    string input_str[L];//存储单词符号
    int str_i = 0;//访问input_str的下标
    
    //字符串数组下标往前移
    void str_i_adv()
    {
      str_i++;
      if(str_i > L-1)
      {
        cout<<"下标越界,请重新输入!";
        exit(0);
        //重新输入
        string str;
        for(int i=0;i<L-1;i++)
        {
          cin>>str;
          //检测输入的结束
          int zero_id = str.find(',', 0);
          //存储识别出来的字母到字符串数组中
          input_str[i] = str.substr(1, zero_id - 1);
        }
      }
    } 
    
    //对表达式进行分析
    void exp_aly()
    {
      //对表达式中的每一个因子做分析
      fac_aly();
      while(input_str[str_i] == "times" || input_str[str_i] == "slash")
      {
        //数组下标前移
        str_i_adv();
        //对表达式中的每一个因子做分析
        fac_aly();
      }
      return;
    } 
    
    //对表达式中的每一个因子做分析
    void fac_aly()
    {
      //判断是否是字母
      if(input_str[str_i] == "ident")
      {
        //数组下标前移
        str_i_adv();
      }
      //判断是否是数字
      else if(input_str[str_i] == "number")
      {
        //数组下标前移
        str_i_adv();
      }
      //判断是否是左括号
      else if(input_str[str_i] == "lparen")
      {
        //数组下标前移
        str_i_adv();
        //对目前的数组进行整体分析
        all_aly();
        //判断是否是右括号
        if(input_str[str_i] == "rparen")
        {
          //数组下标前移
          str_i_adv();
        }
        else {
          cout<<"ERROR!"<<endl;
          exit(0);
        }
      }
      return;
    }
    
    //对目前的表达式进行整体分析
    void all_aly()
    {
      if(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
      }
      exp_aly();
      while(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
        exp_aly();
      }
      return;
    } 
    
    int main()
    {
      string str;
      //输入词法分析的结果
      for(int i=0;i<L-1;i++)
      {
        cin>>str;
        //检测输入的结束
        int zero_id = str.find(',', 0);
        //存储识别出来的字母到字符串数组中
        input_str[i] = str.substr(1, zero_id - 1);
      } 
      //对字符串数组中的表达式进行分析
      if(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
      }
      //表达式分析
      exp_aly();
      while(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
         //数组下标前移
        str_i_adv();
        //表达式分析
        exp_aly();
      }
      if(str_i == L-1) cout<<"Yes,it is correct."<<endl;
      else cout<<"No,it is wrong.";
      return 0;
    }
    

    5 调试数据

    (1)测试样例如下

    【样例输入】
    (lparen,()
    (ident,a)
    (plus,+)
    (number,15)
    (rparen,))
    (times,*)
    (ident,b) 
    
    【样例输出】
    Yes,it is correct.
    

    (2)测试样例结果如下

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v1QuvnUG-1634695547344)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBED1.tmp.jpg)]

    图5 样例测试结果

    6 思考:词法分析+语法分析

    6.1 将实验一的词法分析作为函数写入语法分析程序

    int main()
    {
      string st1r;
      //输入源程序
      for(int i=0;i<L-1;i++)
      {
        cin>>str1;
        //检测输入的结束
        string str;
        str = fun_cifa(str1);//调用词法分析子程序
        int zero_id = str.find(',', 0);
        //存储识别出来的字母到字符串数组中
        input_str[i] = str.substr(1, zero_id - 1);
      }
      //对字符串数组中的表达式进行分析
      if(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
      }
      //表达式分析
      exp_aly();
      while(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
         //数组下标前移
        str_i_adv();
        //表达式分析
        exp_aly();
      }
      if(str_i == L-1) cout<<"Yes,it is correct."<<endl;
      else cout<<"No,it is wrong.";
      return 0;
    }
    

    6.2 调试数据

    【样例输入】
    (a+15)*b
    
    【样例输出】
    (lparen,()
    (ident,a)
    (plus,+)
    (number,15)
    (rparen,))
    (times,*)
    (ident,b)
    Yes,it is correct.
    

    6.3 调试结果

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RRDxtJde-1634695547346)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEE2.tmp.jpg)]

    图6 样例测试结果

    7 实验调试情况及体会

    7.1 实验调试情况

    由上两步中的测试样例可以得到,所有的测试样例均得到了相应的输出结果,说明代码编写成功,并且在代码中设置了出错处理,以便解决其他情况。

    本次实验同时也实现了词法分析与语法分析合在一起去识别源程序的程序,但依然存在一些问题,比如语句只能一句一句地去识别,而不能进行整体识别,该问题会在后续过程中加以解决。

    7.2 实验体会

    这次实验采用的方法是自上而下分析中的递归下降分析法,首先画出了递归下降分析的语法图,然后判断文法是否属于LL(1)文法,最后写出了递归下降的子程序,并写出了代码,在代码中即可以调用上次词法分析的程序,直接对输入的字符串进行分割传入字符串str。

    通过这次实验对于LL(1)文法的三个条件有了更深刻的认识,以及加深对于first 和follow 集合的求法,并且独立完成递归调用函数的书写和实现,对于递归思想又有了进一步的认识,要写函数结束出口,防止函数进入死循环。

    通过这次实验进一步了解了自上而下的语法分析:对于输入的词法分析结果,进行左推导,得到一个合法句子或者非法结构,是一种递归和试探的方法,并且自上而下建立输入序列的分析树,而且需要消除左递归并且提取公因子,进一步理解了理论课所学的具体内容,加深对于一些自上而下课后题的理解。这次实验课的收获很大。

    最后,感谢刘善梅老师和其他同学在这次实验中给予我的帮助,不胜感激!

    展开全文
  • 今天就要开始正式写表达式解析器了,第一章的核心代码一共二十行都不到,包简单包学会,但是里面涉及的原理知识可能要花点时间讲一讲。首先为了能快速简单的开始写我们的解析器,先要对表达式的规则做一定简化:暂时...
  • 编译原理——语法分析器(SLR) 识别语法结构: 变量声明(不含变量初始化) if单条件分支语句以及if else 双条件分支语句 for循环和while循环语句 赋值语句 ,四则运算,逻辑判断复合语句 函数声明 函数调用 文法...
  • 上接语法分析 先使用词法分析得到二元组,用语法分析二元组看表达式语法是否正确,如果正确,计算表达式的值,如果错误,输出语法错误信息。 测试程序: // pL/0语言词法分析器 #include<bits/stdc++.h...
  • 语法解析,顾名思义就是将一个文件或者一段代码,按照语法结构拆分为一个一个的单词,比如: extern int TakeProfit = 50; int start() { int i = 0; while ( i < TakeProfit) { i++; } return(i); } ...
  • 编译原理】理解BNF

    千次阅读 2021-01-20 14:23:28
    解析源码的本质就是将一维的字符串序列转换为一颗语法树。这个可以自己对着源码理解,代码中的缩进就是一种树层次的体现。 BNF范式 BNF范式本质上就是树形分解,很简单嘛。 前端代码解析的难点就在于BNF,对于对...
  • Java的编译原理

    2021-02-12 09:45:06
    概述java语言的"编译期"分为前端编译和...在编译原理中, 将源代码编译成机器码, 主要经过下面几个步骤:Java中的前端编译java的前端编译(即javac编译)可分为解析与填充符号表、插入式注解处理器的注解处理、分析与字...
  • python在收到代码内容后,首先要启动两个流程,分别为词法解析和语法解析。看过我编译原理课程的同学对这两个流程应该不陌生。词法解析其实就是把代码里面不同的元素分别归类,例如234,1.35,1e3等这类字符串统一用...
  • 最近在学习编译原理相关知识,主要看的是编译器前端分析技术,主要学习的有词法分析、语法分析、语义分析、有限自动机、上下文无关文法、BNF范式、语法分析树等相关前端概念内容,后续可能使用Anltr或Peg对特定的DSL...
  • 转自http://blog.sina.com.cn/s/blog_733bf6e00100v1b2.html关于编译原理语法树 句柄 简单短语 短语 的区分,通过两个例子来理解概念以及方法:例子1——语法树S->a|b|(T)T -> TdS|SVt={a,b,d,(,)}.Vn={S,T},S...
  • 编译原理知识汇总

    2021-08-26 11:53:13
    编译原理学习笔记, 超万字的编译原理知识总结...............
  • 编译原理语义分析程序设计》由会员分享,可在线阅读,更多相关《编译原理语义分析程序设计(9页珍藏版)》请在人人文库网上搜索。1、实验3 语义分析程序设计【实验目的】加深对语法制导翻译原理的理解,掌握将语法...
  • 1、参考书籍:《编译原理》第三版 清华大学出版社 1、本文内容全部来源于开源社区 GitHub和以上博主的贡献,本文也免费开源(可能会存在问题,评论区等待大佬们的指正) 2、本文目的:开源共享 抛砖引玉 一起学习 3...
  • 华中科技大学编译原理实验四攻略|完整版

    千次阅读 多人点赞 2021-12-08 10:05:55
    助力来年编译原理加大难度!(hhh) MiniC语法分析及中间代码生成 我根据我的实验报告重置了攻略。 贴个完成时间。 文章目录 MiniC语法分析及中间代码生成 实验内容 实验过程 LLVM IR初识 LLVM IR API 语义分析与中间...
  • java学习编译原理

    2021-03-05 21:16:49
    编写一个.java文件 编写一个.java文件 5-2:通过javac和java指令执行 这个运行过程就不赘述了,我们直接上图: java跨平台原理 5-3:揭秘第一部分.java文件如何变为.class文件 编译器遵守什么规则,将.java文件编译为....
  • 编译原理词法分析程序实验报告解析编译原理实验报告实验名称:编写词法分析程序实验类型:设计性实验指导教师:*****专业班级:软件工程1401姓 名:****学 号:**********实验地点:东六E座301实验成绩:___________...
  • Javac编译原理

    2021-03-05 21:17:13
    机器语言(不同平台不同种类)如何让java的语法规则适应java虚拟机的语法规则?这个任务由javac编译器来完成java语言规范转换成java虚拟机语言规范。编译流程:流程:词法分析器:将源码转换为Token流将源代码划分成一...
  • 编译原理实现计算器

    2021-04-28 07:59:31
    如果表达式语法正确,则输出计算结果,否则报错,指出错误位置及原因。“;”结束;加减乘除;支持括号;;数字和字母print()函数,输出并换行;print()函数不仅可以输出变量,还可以直接输出表达式的值,例如print...
  • calc编译原理实战之表达式计算器前言整理硬盘时翻出之前写的一个简单的表达式计算器, 想想当初为了理解这东西也费了不少功夫, 所以想写一篇笔记, 希望能给当初像我一样的菜鸟一点帮助. 原来只打算写表达式解析计算的...
  • /* * 解析操作 * @str 字符串起始地址 * @len 字符串长度 * @out 用于解析后的token队列,如果解析失败,则不改变 * @return 错误信息 */ extern LexicalAnalysisResult Parse(const char *str, unsigned int len, ...
  • 实验要求 实验三 语法分析程序 (一)学习经典的语法分析器 一、实验目的 学习已有编译器的经典语法分析源...TINY语言请参考《编译原理及实践》第3.7节。对TINY语言要特别注意抽象语法树的定义与应用。 (3)测试语
  • 自上而下分析语法——LL语法 1)消除左递归 2) 消除回溯、提左因子 、 FIRST集 和 FOLLOW 集 3)预测分析法 与 FIRST集 和 FOLLOW 集的构建。 4)预测分析法中 预测分析表M的构建 四、自下而上的分析语法——算符...
  • Vue2.0模板编译原理

    2020-12-29 16:53:37
    将模板解析成AST(Abstract Syntax Tree,抽象语法树) 遍历AST标记静态节点。这样在虚拟DOM中更新节点时,如果发现有静态标记,则不会重新渲染它。 使用AST生成渲染函数 二、解析解析器内部分了好几个子解析...
  • 编译原理初学者入门指南

    千次阅读 2021-01-20 18:00:00
    对工程师来说,解决问题的第一步就是先知道你面对的是什么问题:使用编译原理的知识来解析开头的表达式,相当于定义一个简陋的 DSL 语言,并编写词法解析器和语法解析器(lexer & parser)来将其转换成 AST(抽象...
  • Vue模板编译原理

    2020-12-22 00:46:09
    Vue中的模板编译是什么 刚接触Vue的同学可能会产生这样的疑问:为什么在...这其实都是Vue模板编译的功劳。 ...Vue会根据其规定的模板语法规则,将其解析成AST语法树(其实就是用一个树状的大对象来描述我们所谓的“HT
  • vue的template里可以填充变量...1、解析器:模板解析成AST(抽象语法树); 2、优化器:遍历AST标记静态节点,这样在虚拟DOM更新节点时避免重新渲染静态节点; 3、代码生成器:使用AST生成render函数。 一、解析
  • 编译原理总结

    2021-10-09 16:41:29
    编译原理总结 编译原理总结 文章目录编译原理总结前言一、编译的过程二、前端1.词法分析2.语法分析2.1 LL分析2.2 LR分析3.语义分析4. 中间代码5. 后端5.1 指令选择5.2 活跃性分析5.3 寄存器分配5.4 数据流分析5.5 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 65,442
精华内容 26,176
关键字:

编译原理语法解析