语法分析_语法分析器 - CSDN
精华内容
参与话题
  • 【编译原理】语法分析(一)

    万次阅读 多人点赞 2017-10-30 14:25:22
    词法分析器把源程序转换成了一个词素序列,这个词素序列将作为输入交由语法分析器进一步处理,语法分析器将构造一棵语法分析树,检测这个词素序列是否符合相应的语法规则。

    词法分析器把源程序转换成了一个词素序列,它让我们知道了一个符号序列’i’、’f’是一个关键词”if”,而一个符号序列’1’、’2’、’3’、’4’是一个常量”1234”等等。但是,词法分析器的工作也到此为止了,它不能说明几个词素之间的关系。例如,对于词素串”int”、”x”、”=”、”1”、”;”,词法分析器不知道它是一个语句;对于词素串”int”、”x”、”==”、”1”、”;”,词法分析器不能检测出它的语法错误。为此,在词法分析之后,还需进行语法分析。

    语法分析器的作用

    我们都知道,在使用某一种程序设计编写程序时,都要遵循一套特定的规则。比如,在C语言中,一个程序由多个函数组成,一个函数由声明和语句组成,一个语句由表达式组成等等。这组规则精确描述了一个良构的程序设计语言的语法。语法分析器能够确定一个源程序的语法结构,能够检测出源程序中的语法错误,并且能够从常见的错误中恢复并继续处理程序的其余部分。

    一个语法分析器从词法分析器获得一个词素序列,并验证这个序列是否可以由源语言的文法生成。语法分析器会构造一棵语法分析树,并把它传递给编译器的其他部分进一步处理,在构建语法分析树的过程中,就验证了这个词素序列是否符合源语言的文法。语法分析器在编译器中的位置如下图:

    20171029_img1

    文法

    一个文法用于系统的描述程序设计语言的构造的语法。一个正确设计的文法给出了一个语言的结构,该结构有助于把源程序翻译为正确的目标代码,也有助于检测错误。

    上下文无关文法

    一个上下文无关文法(下文简称文法)由终结符号、非终结符号、一个开始符号和一组产生式组成:

    20171029_img2

    对于产生式头相同的两个或多个产生式,可以把它们的产生式体用“|”连接写成一个产生式。例如,对产生式E→E+TE→T,可以写成E→E+T|T

    一个贯穿全文的表达式文法

    在进入主题之前,先给出一个简单的表达式文法,把它称为文法G,它将作为一个贯穿全文的例子:

        E→E+T|T
        TT*F|F
        F→(E)|id

    在文法G中,有3个产生式。其中,符号”+”、”*”、”(“、”)”、”id”是终结符号,符号”E”、”T”、”F”是非终结符号;符号E是开始符号,表示文法G可以生成的语言。

    关于符号的约定

    在下文中由于需要会出现大量的符号,为了减少冗余和方便理解,我们在此对使用的符号有如下约定:

    • 大写字母表示非终结符号,如A、B、C等;
    • 希腊字母表示任意由非终结符号和终结符号组成的串或者空串,如α、β、γ等。

    推导和规约

    语法分析器在构建一棵语法分析树时,常用的方法可以分为自顶向下和自底向上的。顾名思义,自顶向下的方法是从语法分析树的根结点开始向叶子结点构造的方法,自底向上的方法是从语法分析树的叶子结点开始向根结点构造的方法。在自顶向下的构造过程中,需要从一个非叶子结点“推导”出其子树;在自底向上的构造中,需要把几个非根结点“规约”成其根结点。

    推导

    从产生式的角度来看,一次推导过程是把产生式的左部替换成产生式的右部的过程。

    20171029_img3

    对文法G,从E到id*id+id的一个最左推导和最右推导分别为:

    20171029_img4

    其中,id*id+id是文法G的一个句子,其他中间步骤是文法G的句型。从此亦可看出,对相同句型的推导过程不唯一。

    推导过程可以用语法分析树表示,从E到id*id+id的最左推导的语法分析过程如下图所示:

    20171029_img5

    每棵语法分析树对应于某一次推导,从左到右把语法分析树的叶子结点连接起来就是文法G的一个句型,也称为语法分析树的结果或边缘,最后一棵语法分析树的叶子结点从左到右连接起来是文法G的一个句子。

    规约

    规约是推导的逆过程,一次规约是把一个与某产生式体相匹配的串替换为该产生式头的非终结符号。

    规约过程可以用于自底向上构造语法分析树。例如,把id*id+id规约成E,这里的每次规约是某次最右推导的逆过程,构造的语法分析树如下图所示:

    20171029_img6

    设计文法

    本节将介绍如何对一个文法进行转换使其更适用于语法分析,这些转换方法包括消除二义性,消除左递归和提取左公因子。

    消除二义性

    如果一个文法可以为某个句子生成多棵语法分析树,那么它就是二义性的,简单地说,二义性文法就是对同一个句子有多个最左推导或多个最右推导的文法。

    考虑下面的文法:

        EE+E
        EE*E
        E→(E)
        E→id

    它对句子id+id*id有两个最左推导,下图给出了推导过程和相应的语法分析树:

    20171029_img7

    可以看出,这两个推导过程反映了加法和乘法的优先级问题,左边的推导乘法优先级比加法高,右边的推导加法的优先级比乘法高。实际上,左边的推导过程更符合我们的观念。

    通过把该文法改写成文法G的形式,可以解决这个二义性问题,该文法和文法G都生成同样的语言。

    消除左递归

    如果一个文法对一个非终结符号A,经过一次或多次推导后得到串Aα,那么这个文法是左递归的。如果该文法中存在形如A→Aα的产生式,则该产生式是立即左递归的。

    在介绍消除文法的左递归之前,我们先介绍如何消除产生式的立即左递归。对任意立即左递归的产生式,可以用下面的方法消除立即左递归:

    20171029_img8

    右边的两个产生式生成的串集合和左边的产生式生成的串集合是相同的,并且右边的两个产生式没有左递归,这样就消除了产生式的左递归。

    现在正式介绍对一个左递归的文法如何消除其左递归。对一个左递归的文法,用下面的方法消除左递归:

    20171029_img9

    对文法G,消除它的左递归:

    1. 将非终结符号排序为E、T、F;
    2. 当i=1时,对符号E,产生式E→E+T|T是立即左递归的,把它替换为E→TE'E'→+TE'|ε
    3. 当i=2时,对符号T,产生式T→T*F|F中没有E,但它是立即左递归的,把它替换为T→FT'T'→*FT'|ε
    4. 当i=3时,对符号F,产生式F→(E)|id中有E,把E替换为TE'后得到F→(TE')|id,它不是立即左递归的,算法结束;
    5. 最后得到的非左递归文法为:
        E→TE'
        E'→+TE'
        T→FT'
        T'→*FT'
        F→(TE')|id

    提取左公因子

    当使用自顶向下的方法构造语法分析树时,如果在“展开”一个非终结符号的结点时,有不止一个产生式可以选择,此时无法明确知道该使用哪一个产生式。为了解决这个问题,我们可以通过改写产生式来推后这个决定,等获得足够的信息后再做出正确的选择。

    例如,对于产生式A→+α|+β,假设α和β开头的符号不同,当看到输入“+”时,不能明确决定使用+α还是+β来替换A,只有继续读入下一个输入,才能确定到底使用哪一个产生式。对此,可以把A→+α|+β转换成A→+A'A'→α|β,这样当看到输入“+”时,可以把A替换为A',再根据后续的输入决定如何替换A'。

    对一个文法提取左公因子,对于每个非终结符号A,找出它的两个或多个选项之间的最长公共前缀α,如果α不是空串,那么将所有头为A的产生式做如下替换:

    20171029_img10

    其中,γ表示所有不以α开头的串,A'是一个新的非终结符号。不断应用这个转换,直到每个非终结符号的任意两个产生式体都没有公共前缀为止。

    fightingZh
    欢迎关注微信公众号fightingZh٩(๑❛ᴗ❛๑)۶

    展开全文
  • 【编译原理】语法分析(三)

    万次阅读 2017-11-02 10:29:54
    常用的语法分析方法包括自顶向下和自底向上的方法,在上一篇文章中已经介绍了自顶向下的语法分析方法,本文将介绍自底向上的语法分析方法。

    常用的语法分析方法包括自顶向下和自底向上的方法,在上一篇文章中已经介绍了自顶向下的语法分析方法,本文将介绍自底向上的语法分析方法。

    文法&约定

    按照惯例,我们给出一个贯穿全文的表达式文法G:

        E→E+T|T
        TT*F|F
        F→(E)|id

    以及使用的符号约定:

    • 大写字母:表示非终结符号,如A、B、C等;
    • 小写字母:表示终结符号,如a、b、c等;
    • 希腊字母:表示由终结符号和非终结符号组成的串或者空串,如α、β、γ、ω等;
    • 开始符号:用S表示文法的开始符号;
    • 结束符号:用$表示结束标记,如输入结束、栈为空等;
    • 空串:用ε表示长度为0的串,即空串。

    自底向上的语法分析

    顾名思义,自底向上的语法分析过程对应于为一个输入串构造语法分析树的过程,它从叶子结点开始逐渐向上到达根结点。和自顶向下的语法分析过程相反,自底向上的语法分析过程把几个叶子结点或中间结点归约成一个中间结点,每次归约是一次最右推导的逆过程,当完成一次自底向上的语法分析后,对相应的输入串可以得到一个反向的最右推导。

    句柄

    对文法G和输入串id*id,我们使用自底向上的方法构造它的语法分析树:

    20171031_img1

    如果从最右边的语法分析树开始,到最左边的语法分析树为止,把每棵语法分析树的根结点用deduce4符号连接起来,那么就可以得到串id*id的一个最右推导:

    Ededuce4Tdeduce4T*Fdeduce4T*iddeduce4F*iddeduce4id*id

    也就是说,对串id*id的自底向上的语法分析过程就是从id*id开始,经过一次次归约,最终得到E的过程。其中,每次归约是某个最右推导的逆过程。

    自底向上的语法分析的关键问题是确定每次对哪一个串进行归约,我们把这个串叫作句柄。正式地,如果Sdeduce4deduce4αAγdeduce4αβγ,那么产生式A→β是αβγ的一个句柄,可以把A→β化简为β,即说β是αβγ的一个句柄。

    对上面得到的串id*id的最右推导,因为有F*iddeduce4id*id,所以第一个id是id*id的一个句柄;又因为有T*iddeduce4F*id,所以F是F*id的一个句柄;依此类推。

    这样的话,对一个输入串ω,假设它的一个最右推导为Sdeduce4α1deduce4α2deduce4deduce4αndeduce4ω,如果我们能知道所有αi(1<=i<=n)和ω的一个句柄,就能使用自底向上的方法构造ω的语法分析树。

    注意,对某个串可能有不止一个句柄,例如二义性文法。

    移入-归约语法分析技术

    移入-归约语法分析是一种通用的自底向上的语法分析技术。它使用一个栈来保存文法符号,并用一个输入缓冲区存放剩余的输入符号,使用这种方法时,句柄在被识别之前都出现在栈顶。

    一个移入-归约语法分析器可以执行四种动作:

    1. 移入:将下一个输入符号压入栈顶;
    2. 归约:被归约的符号串的右端必然是栈顶,语法分析器在栈中确定这个串的左端,并决定用哪个非终结符号来替换这个串;
    3. 接受:宣布语法分析过程成功完成;
    4. 报错:发现一个语法错误,并调用一个错误恢复子例程。

    对输入串id*id,它的一个移入-归约语法分析过程如下:

    20171031_img2

    在上图中,栈的顶部在右边,并且每次句柄出现时都在栈顶。这里我们并没有介绍什么时候执行移入,什么时候执行归约,即如何识别一个句柄。下一节内容将介绍一种发现句柄的方法。

    另外,还需要注意的是,在移入-归约语法分析过程中,可能会产生冲突,包括移入/归约冲突和归约/归约冲突。移入/归约冲突是指在移入-归约语法分析的某一步中,既可以执行移入动作,也可以执行归约动作,从而发生的冲突。归约/归约冲突是指在移入-归约语法分析的某一步中,栈顶的句柄可以选择归约成两个或多个产生式头,从而发生的冲突。

    简单LR技术:SLR

    目前最流行的自底向上的语法分析器都基于所谓的LR(k)语法分析的概念。其中,“L”表示对输入进行从左到右的扫描,“R”表示反向构造一个最右推导序列,“k”表示在做出语法分析决定时向前看k个输入符号。当省略(k)时,假设k=1。

    本节将介绍简单LR技术(简称为SLR),它是一种最简单的构造移入-归约语法分析器的方法。SLR依赖于一张语法分析表,该语法分析表包括ACTION和GOTO集合,它们是根据LR(0)自动机得到的,一个LR(0)自动机由一个状态集合和一个转移函数组成。

    规范LR(0)项和LR(0)自动机

    一个LR语法分析器通过维护一些状态,用这些状态来表明在语法分析过程中所处的位置,从而做出移入-归约决定。

    一个文法的一个LR(0)项(简称为项)是该文法的一个产生式加上一个位于它的体中某处的点。举个例子,对产生式A→αβγ来说,它有四个项,分别为A→·αβγ、A→α·βγ、A→αβ·γ和A→αβγ·。项A→·αβγ表明我们希望在接下来的输入中看到一个可以从αβγ推导得到的串;项A→α·βγ表明我们刚刚在输入中看到了一个可以从α推导得到的串,并且我们希望在接下来的输入中看到一个可以从βγ推导得到的串;项A→αβγ·表明我们已经在输入中看到了一个可以从αβγ推导得到的串,并且是时候把这个串归约为A了。

    一个或多个项可以组成一个项集,而一组项集提供了构建一个DFA的基础,这个DFA可用于做出语法分析决定,这样的DFA称为LR(0)自动机。

    LR(0)自动机的每个状态代表一个项集。为了确定LR(0)自动机的每个状态代表的项集中包含哪些项,我们需要用到两个函数CLOSURE和GOTO,这两个函数的作用有点类似于DFA的ε-closure和move函数。

    对文法的一个项集I,CLOSURE(I)的构造规则如下:

    1. 把I中的所有项加入CLOSURE(I)中;
    2. 如果A→α·Bβ在CLOSURE(I)中,B→γ是一个产生式,并且B→·γ不在不在CLOSURE(I)中,就把项B→·γ加入CLOSURE(I)中。不断应用这个规则,直到没有新项可以加入CLOSURE(I)中为止。

    对文法G,计算项集{ E→·E+T }的CLOSURE集合的过程如下:

    1. 把项E→·E+T加入CLOSURE集合中;
    2. 由于E→T是一个产生式,且E→·T不在CLOSURE集合中,因此把它加入CLOSURE集合中;
    3. 由于T→T*F|F是一个产生式,且T→·T*FT→·F都不在CLOSURE集合中,因此把它们加入CLOSURE集合中;
    4. 由于F→(E)|id是一个产生式,且F→·(E)F→·id都不在CLOSURE集合中,因此把它们加入CLOSURE集合中。到此,已经没有新的项可以加入CLOSURE集合中,最终的CLOSURE集合为:
        E→·E+T
        E→·T
        T→·T*F
        T→·F
        F→·(E)
        F→·id

    对文法的一个项集I和一个文法符号X,GOTO(I, X)的构造规则如下:

    1. 如果A→α·Xβ在I中,就把项A→αX·β加入GOTO(I, X)中;
    2. 把GOTO(I, X)作为CLOSURE函数的参数,计算GOTO(I, X)的闭包。

    对上面得到的项集{ E→·E+T }的CLOSURE集合和符号“(”,计算它的GOTO集合的过程如下:

    1. 把项F→(·E)加入GOTO集合中;
    2. 由于E→E+T|T是一个产生式,且E→·E+TE→·T都不在GOTO集合中,因此把它们加入GOTO集合中;
    3. 由于T→T*F|F是一个产生式,且T→·T*FT→·F都不在GOTO集合中,因此把它们加入GOTO集合中;
    4. 由于F→(E)|id是一个产生式,且F→·(E)F→·id都不在GOTO集合中,因此把它们加入GOTO集合中。到此,已经没有新的项可以加入GOTO集合中,最终的GOTO集合为:
        F→(·E)
        E→·E+T
        E→·T
        T→·T*F
        T→·F
        F→·(E)
        F→·id

    到此,我们已经知道如何确定LR(0)自动机的每个状态(CLOSURE函数)和转移函数(GOTO函数)。另外,为了规范一个文法的LR(0)自动机,我们把该文法表示为一个增广文法,即在该文法中加入新的开始符号S’和产生式S’→S得到的文法。引入这个新的开始符号和产生式的目的是告诉语法分析器何时应该停止语法分析并宣称接受输入符号串。也就是说,当且仅当语法分析器使用S’→S进行归约时,输入符号串被接受。

    文法G的增广文法的LR(0)自动机如下:

    20171031_img3

    LR(0)自动机是如何帮助做出移入-归约决定的呢?假设串γ使LR(0)自动机从开始状态0运行到某个状态j,如果下一个输入符号为a且状态j有一个在a上的转换,就移入a,否则进行归约操作,状态j的项将告诉我们使用哪个产生式进行归约。

    对文法G和输入串id*id,使用上面给出的文法G的LR(0)自动机对它进行移入-归约语法分析的过程如下:

    20171031_img4

    实际上,在一个LR语法分析器中,LR(0)自动机会被转换成一张LR语法分析表,在下一小节中,我们继续介绍如何从LR(0)自动机构建LR语法分析表。

    LR语法分析表

    一个LR语法分析器的语法分析表由一个语法分析动作函数ACTION和一个转换函数GOTO组成:

    • ACTION函数:ACTION函数有两个参数,一个是状态i,一个是终结符号(包括输入结束标记$)a,ACTION[i, a]有四种取值:
      1. 移入。如果状态i上有一个转移a到达状态j,那么ACTION[i, a]=移入j;
      2. 归约。如果状态i上没有一个转移a,那么ACTION[i, a]=按照状态i上的产生式进行归约;
      3. 接受。语法分析器接受输入并完成语法分析过程;
      4. 报错。语法分析器在它的输入中发现一个错误并执行某个纠正动作。
    • GOTO函数:实质上和项集的GOTO函数一样,只不过把项集替换成了状态。即:如果对项集的GOTO函数,有GOTO[Ii, A]=Ij,那么对LR语法分析表的GOTO函数,有GOTO[i, A]=j。

    根据一个LR(0)自动机,我们可以立马得出LR语法分析表的GOTO函数,但是,对ACTION函数,应用下面的规则计算:

    1. 在LR(0)自动机中,如果项A→α·aβ在项集Ii中并且GOTO[Ii, a]=Ij,那么将ACTION[i, a]设为“移入j”;
    2. 在LR(0)自动机中,如果项A→α·在项集Ii中,那么对于FOLLOW(A)中的所有a,将ACTION[i, a]设为“按照A→α归约”,这里A不等于S’;
    3. 在LR(0)自动机中,如果项S’→S·在项集Ii中,那么将ACTION[i, $]设为“接受”。

    除此之外,将所有空白的ACTION和GOTO设为“报错”。

    PS:如果不清楚如何计算FOLLOW函数,可以浏览上一篇文章【编译原理】语法分析(二)

    现在尝试对文法G构建LR语法分析表,为了方便,我们对文法G中的每个产生式进行编号:

        (1) E→E+T    (2) E→T
        (3) TT*F    (4) TF
        (5) F→(E)    (6) F→id

    并约定ACTION函数中的每个符号的意义:

    • si表示移入并将状态i压栈;
    • rj表示按照序号为j的产生式进行归约;
    • acc表示接受;
    • 空白表示报错。

    得到的LR语法分析表如下:

    20171031_img5

    PS:对每个终结符号的ACTION函数,如果ACTION函数取值为移入,那么其实质就是GOTO函数。

    为了说明LR语法分析表的使用方法,这里举一个例子:维护一个状态栈,初始时状态0位于栈顶,如果下一个输入符号是“id”,则将状态5压栈;位于状态5时,如果下一个输入符号是“*”,则使用产生式F→id进行归约,把id替换成F并将状态5从栈顶弹出,此时位于状态0(状态0在栈顶),由于状态0经过符号F的转移到达状态3,因此将状态3压栈;依次类推。对LR语法分析表完整系统的使用方法将在下一小节介绍。

    LR语法分析算法

    一个LR语法分析器由一个输入缓冲区、一个状态栈、一个语法分析表和一个结果输出组成,如下图所示:

    20171031_img6

    语法分析表在上一小节中已经介绍过了,这里重点说一下状态栈。状态栈维护一个状态序列s0s1…sn,其中sn位于栈顶,每个状态si对应于LR(0)状态机中的某个状态,并且除了初始状态之外,每个状态都有一个唯一的相关联的文法符号。也就是说,在LR(0)状态机中,如果从Ii经过符号α转移到Ij,那么状态j的关联符号为α。

    用状态栈和剩余的输入符号串可以完整的表示语法分析器在某一刻的状态,这个状态本质上是反向最右推导中的某个句型。我们用(s0s1…sm, a1a2…an$)表示语法分析器的状态,并称其为语法分析器的格局。其中,第一个分量是状态栈中的状态序列(sm是栈顶),第二个分量是剩余的输入符号串,如果把第一个分量中的每个状态替换为其关联的文法符号,再与第二个分量连接,就能得到反向最右推导中的一个句型。

    假定LR语法分析器当前的格局为(s0s1…sm, aiai+1…an$),在根据当前格局决定下一个动作时,首先读入下一个输入的符号ai和栈顶的状态sm,然后查询LR语法分析表中的条目ACTION[sm, ai],执行相应的动作:

    1. 如果ACTION[sm, ai]=移入s,那么将状态s压入栈顶,格局变为(s0s1…sms, ai+1ai+2…an$);
    2. 如果ACTION[sm, ai]=按照A→β归约,那么将r(r是β的长度)个状态从栈顶弹出,并将状态s(s=GOTO[sm-r, A])压入栈顶,格局变为(s0s1…sm-rs, aiai+1…an$)。注意,在执行归约动作时,当前的输入符号不会改变;
    3. 如果ACTION[sm, ai]=接受,那么语法分析过程完成;
    4. 如果ACTION[sm, ai]=报错,那么语法分析器发现了一个语法错误,并调用一个错误恢复例程。

    综上所述,一个LR语法分析器和LL语法分析器一样,也是表驱动的。两个LR语法分析器的唯一不同之处在于它们的语法分析表不同。

    现在对文法G和输入符号串id*id+id,相应的LR语法分析表已经在上面得到了,分析其LR语法分析过程:

    20171031_img7

    其中,状态栈的栈顶在右侧,符号是栈中每个状态关联的文法符号(初始状态0没有相关联的文法符号),并且,从最后一行开始到第一行,把每行的符号和输入连接起来得到文法G的一个句型,把这些句型用deduce4符号连接起来(除去重复的句型),就得到一个最右推导。

    fightingZh
    欢迎关注微信公众号fightingZh٩(๑❛ᴗ❛๑)۶

    展开全文
  • 编译器----语法分析

    千次阅读 2018-05-31 10:15:02
    语法分析任务是在词法分析识别出单词符号的基础上,分析源程序的语法结构,即分析由这些单词如何组成各种语法成分,比如“声明”、“函数”、“语句”、“表达式”等,并分析判断程序的语法结构是否复合语法规则。...

    本文通过学习王博俊、张宇的《DIY Compiler and Linker》 ,实现语法分析器,一方面作为自己的学习笔记,一方面也作与大家分享与交流

    代码放在github上

    一、语法分析的任务

    语法分析任务是在词法分析识别出单词符号的基础上,分析源程序的语法结构,即分析由这些单词如何组成各种语法成分,比如“声明”、“函数”、“语句”、“表达式”等,并分析判断程序的语法结构是否复合语法规则。

    语法分析分为自上而下和自下而上两个大类,自上而下核心思路是推导,自下而上核心思路是规约,本语法分析采用自上而下的方法。

    在《编译原理》课上学到,自上而下方法需要避免左递归、消除回溯。自上而下分析方法分为两种:递归子程序法和预测分析方法,这里采用递归子程序法。

    二、语法定义

    在实现语法分析之前,先对语言的语法进行定义。

    先列出巴科斯范式(EBNF)语法符号表,以防看不懂语法定义:

    EBNF元符号 含义
    ::= 意思是“推导为”
    |
    {} 含0次在内任意多次重复
    [] 含0次和1次重复
    () 括号内看作一项
    . 一条生成规则的结束
    <> 非终结符
    “” 终结符

    2.1 外部定义

    <翻译单元>::={<外部声明>}<文件结束符>
    
    <外部声明>::=<函数定义>|<声明>

    2.1.1 函数定义

    <函数定义>::=<类型区分符><声明符><函数体>
    
    <函数体>::=<复合语句>

    2.1.2 声明

    <声明>::=<类型区分符>[<初值声明符表>]<分号>
    
    <初值声明符表>::=<初值声明符>{<逗号><初值声明符>}
    
    <初值声明符>::=<声明符>|<声明符><赋值运算符><初值符>

    2.1.3 类型区分符

    <类型区分符>::=<void关键字>|<char关键字>|<short关键字>|<int关键字>|<结构区分符>
    
    <结构区分符>::=<struct关键字><标识符><左大括号><结构声明表><右大括号>|<struct关键字><标识符>
    
    <结构声明表>::=<结构声明>{<结构声明>}
    
    <结构声明>::=<类型区分符>{<结构声明符表>}<分号>
    
    <结构声明符表>::=<声明符>{<逗号><声明符>}

    2.1.4 声明符

    <声明符>::={<指针>}[<调用约定>][<结构体成员对齐>]<直接声明符>
    
    <调用约定>::=<__cdecl关键字>|<__stdcall关键字>
    
    <结构体成员对齐>::=<__align关键字><左小括号><整数常量><右小括号>
    
    <指针>::=<星号>
    
    <直接声明符>::=<标识符><直接声明符后缀>
    
    <直接声明符后缀>::={<左中括号><右中括号>
        |<左中括号><整数常量><右中括号>
        |<左小括号><右小括号>
        |<左小括号><形参表><右小括号>}
    
    <参数声明>::=<类型区分符><声明符>

    2.1.5 初值符

    <初值符>::=<赋值表达式>

    2.2 语句

    <语句>::={<复合语句>|
            <if语句>|
            <for语句>|
            <break语句>|
            <continue语句>|
            <return语句>|
            <表达式语句>}

    2.2.1 复合语句

    <复合语句>::=<左大括号>{<声明>}{<语句>}<右大括号>

    2.2.2 表达式语句与空语句

    <表达式语句>::=[<expression>]<分号>

    2.2.3 选择语句

    <if语句>::=<if关键字><左小括号><表达式><右小括号><语句>[<else关键字><语句>]

    2.2.4 循环语句

    <for语句>::=<for关键字><左小括号><表达式语句><表达式语句><表达式><右小括号><语句>

    2.2.5 跳转语句

    <continue语句>::=<continue关键字><分号>
    
    <break语句>::=<break关键字><分号>
    
    <return语句>::=<return关键字><expression><分号>

    2.3 表达式

    <表达式>::=<赋值表达式>{<逗号><赋值表达式>}

    2.3.1 赋值表达式

    <赋值表达式>::=<相等类表达式>|<一元表达式><赋值等号><赋值表达式>

    2.3.2 相等类表达式

    <相等类表达式>::=<关系表达式>{<等于号><关系表达式>|<不等于号><关系表达式>}

    2.3.3 关系表达式

    <关系表达式>::=<加减类表达式>{
                <小于号><加减类表达式>
                |<大于号><加减类表达式>
                |<小于等于号><加减类表达式>
                |<大于等于号><加减类表达式>}

    2.3.4 加减类表达式

    <加减类表达式>::=<乘除类表达式>{
                <加号><乘除类表达式>
                <减号><乘除类表达式>}

    2.3.5 乘除类表达式

    <乘除类表达式>::=<一元表达式>{
                <星号><一元表达式>
                |<除号><一元表达式>
                |<取余运算符><一元表达式>}

    2.3.6 一元表达式

    <一元表达式>::=<后缀表达式>
                |<与号><一元表达式>
                |<星号><一元表达式>
                |<加号><一元表达式>
                |<减号><一元表达式>
                |<sizeof表达式>
    
    <sizeof表达式>::=<sizeof关键字>(<类型区分符>)

    2.3.7 后缀表达式

    <后缀表达式>::=<初等表达式>{
                <左中括号><expression><右中括号>
                |<左小括号><右小括号>
                |<左小括号><实参表达式表><右小括号>
                |<点号>IDENTIFIER
                |<箭头>IDENTIFIER}
    
    <实参表达式表>::=<赋值表达式>{<逗号><赋值表达式>}

    2.3.8 初等表达式

    <初等表达式>::=<标识符>|<整数常量>|<字符串常量>|<字符常量>|(<表达式>)

    三、语法分析的实现

    为了将语法分析表示出来,我们给源代码进行语法缩进,来表示顺利实现语法分析

    语法缩进由两个全局变量控制:

    int syntax_state;  //语法状态
    int syntax_level;  //缩进级别

    语法状态取值为:

    enum e_SynTaxState
    {
        SNTX_NUL,       // 空状态,没有语法缩进动作
        SNTX_SP,        // 空格 int a; int __stdcall MessageBoxA(); return 1;
        SNTX_LF_HT,     // 换行并缩进,每一个声明、函数定义、语句结束都要置为此状态
        SNTX_DELAY      // 延迟取出下一单词后确定输出格式,取出下一个单词后,根据单词类型单独调用syntax_indent确定格式进行输出 
    };

    通过Tab键控制缩进级别:

    void print_tab(int n)
    {
        int i = 0;
        for (; i < n; i++)
            printf("\t");
    }

    语法缩进程序为:

    void syntax_indent()
    {
        switch (syntax_state)
        {
        case SNTX_NUL:
            color_token(LEX_NORMAL);
            break;
        case SNTX_SP:
            printf(" ");
            color_token(LEX_NORMAL);
            break;
        case SNTX_LF_HT:
        {
            if (token == TK_END)        // 遇到'}',缩进减少一级
                syntax_level--;
            printf("\n");
            print_tab(syntax_level);
        }
        color_token(LEX_NORMAL);
        break;
        case SNTX_DELAY:
            break;
        }
        syntax_state = SNTX_NUL;
    }

    不仅延续之间词法分析的词法着色,并且加上了语法缩进

    每次在取单词时执行syntax_indent()函数

    void get_token()
    {
        ...
        syntax_indent();
    }

    3.1 外部定义语法分析

    语法定义:

    <翻译单元>::={<外部声明>}<文件结束符>
    <外部声明>::=<函数定义>|<声明>
    
    <函数定义>::=<类型区分符><声明符><函数体>
    <函数体>::=<复合语句>
    
    <声明>::=<类型区分符>[<初值声明符表>]<分号>
    <初值声明符表>::=<初值声明符>{<逗号><初值声明符>}
    <初值声明符>::=<声明符>|<声明符><赋值运算符><初值符>
    
    <类型区分符>::=<void关键字>|<char关键字>|<short关键字>|<int关键字>|<结构区分符>
    <结构区分符>::=<struct关键字><标识符><左大括号><结构声明表><右大括号>|<struct关键字><标识符>
    <结构声明表>::=<结构声明>{<结构声明>}
    <结构声明>::=<类型区分符>{<结构声明符表>}<分号>
    <结构声明符表>::=<声明符>{<逗号><声明符>}
    
    <声明符>::={<指针>}[<调用约定>][<结构体成员对齐>]<直接声明符>
    <调用约定>::=<__cdecl关键字>|<__stdcall关键字>
    <结构体成员对齐>::=<__align关键字><左小括号><整数常量><右小括号>
    <指针>::=<星号>
    <直接声明符>::=<标识符><直接声明符后缀>
    <直接声明符后缀>::={<左中括号><右中括号>
        |<左中括号><整数常量><右中括号>
        |<左小括号><右小括号>
        |<左小括号><形参表><右小括号>}
    <参数声明>::=<类型区分符><声明符>
    
    <初值符>::=<赋值表达式>

    3.1.1 翻译单元

    翻译单元的语法定义:

    <translation_unit>::={external_declaration}<TK_EOF>

    翻译单元的语法描述图:
    这里写图片描述
    翻译单元的代码:

    void translation_unit()
    {
        while (token != TK_EOF)
        {
            external_declaration(SC_GLOBAL);
        }
    }

    3.1.2 外部声明

    外部声明的语法定义:

    <external_declaration>::=<function_definition>|<declaration>
    <function_definition>::= <type_specifier> <declarator><funcbody>
    <declaration>::= <type_specifier><TK_SEMICOLON>|<type_specifier>< init_declarator_list><TK_SEMICOLON>
    <init_declarator_list>::=<init_declarator>{<TK_COMMA> <init_declarator>}
    <init_declarator>::=<declarator>|<declarator> <TK_ASSIGN><initializer>

    等价转换后可以得到外部声明的语法定义:

    <external_declaration>::=<type_specifier> (<TK_SEMICOLON>
    |<declarator><funcbody>
    |<declarator>[<TK_ASSIGN><initializer>]
    {<TK_COMMA><declarator>[<TK_ASSIGN><initializer>]}
    <TK_SEMICOLON>)

    外部声明的语法描述图:
    这里写图片描述
    外部声明的语法分析函数:

    void external_declaration(int l)
    {
        if (!type_specifier())
        {
            expect("<类型区分符>");
        }
    
        if (token == TK_SEMICOLON) //如果取词到分号
        {
            get_token();
            return;
        }
        while (1)// 逐个分析声明或函数定义
        {
            declarator();
            if (token == TK_BEGIN)
            {
                if (l == SC_LOCAL)
                    error("不支持函数嵌套定义");
                funcbody();
                break;
            }
            else
            {
                if (token == TK_ASSIGN)
                {
                    get_token();
                    initializer();
                }
    
                if (token == TK_COMMA)
                {
                    get_token();
                }
                else
                {
                    syntax_state = SNTX_LF_HT;
                    skip(TK_SEMICOLON);
                    break;
                }
            }
        }
    }

    3.1.3 类型区分符

    类型区分符的语法定义:

    <type_specifier>::= <KW_INT>
            | <KW_CHAR>
            | <KW_SHORT>
            | <KW_VOID >
            | <struct_specifier>

    类型区分符的语法描述图:
    这里写图片描述
    外部声明的语法分析函数:

    int type_specifier()
    {
        int type_found = 0;
        switch (token)
        {
        case KW_CHAR:
            type_found = 1;
            syntax_state = SNTX_SP;
            get_token();
            break;
        case KW_SHORT:
            type_found = 1;
            syntax_state = SNTX_SP;
            get_token();
            break;
        case KW_VOID:
            type_found = 1;
            syntax_state = SNTX_SP;
            get_token();
            break;
        case KW_INT:
            syntax_state = SNTX_SP;
            type_found = 1;
            get_token();
            break;
        case KW_STRUCT:
            syntax_state = SNTX_SP;
            struct_specifier();
            type_found = 1;
            break;
        default:
            break;
        }
        return type_found;
    }

    3.1.4 结构区分符

    结构区分符的语法定义:

    <struct_specifier>::=
        <KW_STRUCT><IDENTIFIER><TK_BEGIN><struct_declaration_list><TK_END>
        | <KW_STRUCT>  <IDENTIFIER>

    结构区分符的语法描述图:
    这里写图片描述
    结构区分符代码:

    void struct_specifier()
    {
        int v;
    
        get_token();    
        v = token;
    
        syntax_state = SNTX_DELAY;      // 新取单词不即时输出,延迟到取出单词后根据单词类型判断输出格式
        get_token();
    
        if(token == TK_BEGIN)           // 适用于结构体定义
            syntax_state = SNTX_LF_HT;
        else if(token == TK_CLOSEPA)    // 适用于 sizeof(struct struct_name)
            syntax_state = SNTX_NUL;
        else                            // 适用于结构变量声明
            syntax_state = SNTX_SP;
        syntax_indent();    
    
        if (v < TK_IDENT)               // 关键字不能作为结构名称
            expect("结构体名");
    
        if (token == TK_BEGIN) 
        {
            struct_declaration_list();
        }
    }
    3.1.4.1 结构声明符表

    结构声明符表的语法定义:

     <struct_declaration_list>::=<struct_declaration>{<struct_declaration>}

    结构声明符表的语法描述图:
    这里写图片描述
    结构声明符表的代码:

    void struct_declaration_list()
    {
        int maxalign, offset;
    
        syntax_state = SNTX_LF_HT;  // 第一个结构体成员与'{'不写在一行
        syntax_level++;             // 结构体成员变量声明,缩进增加一级
    
        get_token();
        while (token != TK_END)
        {
            struct_declaration(&maxalign, &offset);
        }
        skip(TK_END);
    
        syntax_state = SNTX_LF_HT;
    }
    3.1.4.2 结构声明

    结构声明的语法定义:

    <struct_declaration>::=
            <type_specifier><struct_declarator_list><TK_SEMICOLON>
    
    <struct_declarator_list>::=<declarator>{<TK_COMMA><declarator>}

    等价转换后语法定义为:

    <struct_declaration>::=
            <type_specifier><declarator>{<TK_COMMA><declarator>}
            <TK_SEMICOLON>

    结构声明的语法描述图:
    这里写图片描述

    结构声明的代码:

    void struct_declaration()
    {
        type_specifier();
        while (1)
        {
            declarator();
    
            if (token == TK_SEMICOLON || token == TK_EOF)
                break;
            skip(TK_COMMA);
        }
        syntax_state = SNTX_LF_HT;
        skip(TK_SEMICOLON);
    }

    3.1.5 声明符

    声明符语法:

    <declarator>::={<pointer>}{<function_calling_convention>}
        {<struct_member_alignment>}<direct_declarator>
    
    <pointer>::=<TK_STAR>

    等价转化后为:

    <declarator>::={<TK_STAR>}[<function_calling_convention>]
        [<struct_member_alignment>]<direct_declarator>

    声明符的语法描述图:
    这里写图片描述

    声明符的代码为:

    void declarator()
    {
        while (token == TK_STAR)
        {
            get_token();
        }
        function_calling_convention();
        struct_member_alignment();
        direct_declarator();
    }
    3.1.5.1 函数调用约定

    函数调用约定语法:

    <function_calling_convention>::=<KW_CDECL>|<KW_STDCALL>

    函数调用约定的描述图:
    这里写图片描述

    函数调用约定的代码:

    void function_calling_convention()
    {
        if (token == KW_CDECL || token == KW_STDCALL)
        {
            syntax_state = SNTX_SP;
            get_token();
        }
    }
    3.1.5.2 结构成员对齐

    结构成员对齐语法:

    <struct_member_alignment>::=<KW_ALIGN><TK_OPENPA><TK_CINT><TK_CLOSEPA>

    结构成员对齐的描述图:
    这里写图片描述

    结构成员对齐的代码:

    void struct_member_alignment()
    {
        if (token == KW_ALIGN)
        {
            get_token();
            skip(TK_OPENPA);
            if (token == TK_CINT)
            {
                get_token();
            }
            else
                expect("整数常量");
            skip(TK_CLOSEPA);
        }
    }
    3.1.5.3 直接声明符

    直接声明符语法:

    <direct_declarator>::=  <IDENTIFIER><direct_declarator_postfix>

    直接声明符的描述图:
    这里写图片描述

    直接声明符的代码:

    void direct_declarator()
    {
        if (token >= TK_IDENT)
        {
            get_token();
        }
        else
        {
            expect("标识符");
        }
        direct_declarator_postfix();
    }
    3.1.5.4 直接声明后缀

    直接声明后缀语法:

    <direct_declarator_ postfix>::= {<TK_OPENBR><TK_CINT><TK_CLOSEBR>
            |<TK_OPENBR><TK_CLOSEBR>
            |<TK_OPENPA><parameter_type_list><TK_CLOSEPA>
            |<TK_OPENPA><TK_CLOSEPA>}

    直接声明后缀描述图:
    这里写图片描述

    直接声明后缀代码:

    void direct_declarator_postfix()
    {
        int n;
    
        if (token == TK_OPENPA)
        {
            parameter_type_list();
        }
        else if (token == TK_OPENBR)
        {
            get_token();
            if (token == TK_CINT)
            {
                get_token();
                n = tkvalue;
            }
            skip(TK_CLOSEBR);
            direct_declarator_postfix();
        }
    }
    3.1.5.5 形参类型表

    形参类型表语法:

    <parameter_type_list>::=<parameter_list>
        |<parameter_list><TK_COMMA><TK_ELLIPSIS>
    
    <parameter_list>::=<parameter_declaration>
        {<TK_COMMA ><parameter_declaration>}
    
    <parameter_declaration>::=<type_specifier>{<declarator>}

    等价转换后语法:

     <parameter_type_list>::=<type_specifier>{<declarator>}
        {<TK_COMMA><type_specifier>{<declarator>}}<TK_COMMA><TK_ELLIPSIS>

    形参类型表语法图:
    这里写图片描述

    形参类型表代码:

    void parameter_type_list()
    {
    
        get_token();
        while (token != TK_CLOSEPA)
        {
            if (!type_specifier())
            {
                error("无效类型标识符");
            }
            declarator();
            if (token == TK_CLOSEPA)
                break;
            skip(TK_COMMA);
            if (token == TK_ELLIPSIS)
            {
                //func_call = KW_CDECL;
                get_token();
                break;
            }
        }
        syntax_state = SNTX_DELAY;
        skip(TK_CLOSEPA);
        if (token == TK_BEGIN)          // 函数定义
            syntax_state = SNTX_LF_HT;
        else                            // 函数声明
            syntax_state = SNTX_NUL;
        syntax_indent();
    }
    3.1.5.6 函数体

    函数体的语法:

    <funcbody>::=<compound_statement>
    

    在这里函数体只推导出复合语句

    函数体的语法图:
    这里写图片描述

    函数体的代码:

    void funcbody()
    {
        compound_statement();
    }
    3.1.5.6 初值符

    初值符的语法:

    < initializer>::=<assignment_expression>

    这里也是初值符只推导出赋值表达式

    初值符的语法图:
    这里写图片描述

    初值符的代码:

    void initializer()
    {
        assignment_expression();
    }

    3.2 语句语法分析

    语法定义:

    <语句>::={<复合语句>|
            <if语句>|
            <for语句>|
            <break语句>|
            <continue语句>|
            <return语句>|
            <表达式语句>}
    
    <复合语句>::=<左大括号>{<声明>}{<语句>}<右大括号>
    
    <表达式语句>::=[<expression>]<分号>
    
    <if语句>::=<if关键字><左小括号><表达式><右小括号><语句>[<else关键字><语句>]
    
    <for语句>::=<for关键字><左小括号><表达式语句><表达式语句><表达式><右小括号><语句>
    
    <continue语句>::=<continue关键字><分号>
    <break语句>::=<break关键字><分号>
    <return语句>::=<return关键字><expression><分号>

    3.2.1 语句

    语句的语法:

    <statement >::=<compound_statement>
            | <if_statement>
            | <return_statement>
            | <break_statement>
            | <continue_statement>
            | <for_statement>
            | <expression_statement>

    语句的语法图:
    这里写图片描述

    语句的代码:

    void statement()
    {
        switch (token)
        {
        case TK_BEGIN:
            compound_statement();
            break;
        case KW_IF:
            if_statement();
            break;
        case KW_RETURN:
            return_statement();
            break;
        case KW_BREAK:
            break_statement();
            break;
        case KW_CONTINUE:
            continue_statement();
            break;
        case KW_FOR:
            for_statement();
            break;
        default:
            expression_statement();
            break;
        }
    }

    3.2.1 复合语句

    复合语句的语法:

    <compound_statement>::=<TK_BEGIN>{<declaration>}{<statement>}<TK_END>

    复合语句的语法图:
    这里写图片描述

    语句的代码:

    void compound_statement()
    {
        syntax_state = SNTX_LF_HT;
        syntax_level++;                     // 复合语句,缩进增加一级
    
        get_token();
        while (is_type_specifier(token))
        {
            external_declaration(SC_LOCAL);
        }
        while (token != TK_END)
        {
            statement();
        }
    
        syntax_state = SNTX_LF_HT;
        get_token();
    }

    复合语句由声明和语句组成,声明在前,语句在后。在应该出现声明的地方用解析声明函数external_declaration(),在应该出现语句的地方用语句解析函数statement()解析语句。

    代码中的is_type_specifier()函数就是根据当前单词判断是否是声明:

    int is_type_specifier(int v)
    {
        switch (v)
        {
        case KW_CHAR:
        case KW_SHORT:
        case KW_INT:
        case KW_VOID:
        case KW_STRUCT:
            return 1;
        default:
            break;
        }
        return 0;
    }

    3.2.2 表达式语句

    表达式语句的语法:

    <expression_statement>::= <TK_SEMICOLON>|<expression> <TK_SEMICOLON>

    表达式语句的语法图:
    这里写图片描述
    表达式语句的代码:

    void expression_statement()
    {
        if (token != TK_SEMICOLON)
        {
            expression();
        }
        syntax_state = SNTX_LF_HT;
        skip(TK_SEMICOLON);
    }

    3.2.3 选择语句

    选择语句的语法:

    <if_statement>::=<KW_IF><TK_OPENPA><expression>
        <TK_CLOSEPA><statement>[<KW_ELSE><statement>]

    选择语句的语法图:
    这里写图片描述
    选择语句的代码:

    void if_statement()
    {
        syntax_state = SNTX_SP;
        get_token();
        skip(TK_OPENPA);
        expression();
        syntax_state = SNTX_LF_HT;
        skip(TK_CLOSEPA);
        statement();
        if (token == KW_ELSE)
        {
            syntax_state = SNTX_LF_HT;
            get_token();
            statement();
        }
    }

    3.2.4 循环语句

    循环语句的语法:

    <for_statement>::=<KW_FOR><TK_OPENPA><expression_statement>
        <expression_statement><expression><TK_CLOSEPA><statement>

    循环语句的语法图:
    这里写图片描述
    循环语句的代码:

    void for_statement()
    {
        get_token();
        skip(TK_OPENPA);
        if (token != TK_SEMICOLON)
        {
            expression();
        }
        skip(TK_SEMICOLON);
        if (token != TK_SEMICOLON)
        {
            expression();
        }
        skip(TK_SEMICOLON);
        if (token != TK_CLOSEPA)
        {
            expression();
        }
        syntax_state = SNTX_LF_HT;
        skip(TK_CLOSEPA);
        statement();//只有此处用到break,及continue,一个循环中可能有多个break,或多个continue,故需要拉链以备反填
    }

    3.2.5 跳转语句

    跳转语句包括continue语句、break语句和return语句

    语法图为:
    这里写图片描述

    3.2.5.1 continue语句

    continue语句的语法:

    <continue_statement>::=<KW_CONTINUE><TK_SEMICOLON>

    continue语句的代码:

    void continue_statement()
    {
        get_token();
        syntax_state = SNTX_LF_HT;
        skip(TK_SEMICOLON);
    }
    3.2.5.2 break语句

    break语句的语法:

    <break_statement>::=<KW_BREAK><TK_SEMICOLON>

    break语句的代码:

    void break_statement()
    {
        get_token();
        syntax_state = SNTX_LF_HT;
        skip(TK_SEMICOLON);
    }
    3.2.5.3 return语句

    return语句的语法:

    <return_statement>::=<KW_RETURN><TK_SEMICOLON>
            |<KW_RETURN><expression><TK_SEMICOLON>

    return语句的代码:

    void return_statement()
    {
        syntax_state = SNTX_DELAY;
        get_token();
        if (token == TK_SEMICOLON)  // 适用于 return;
            syntax_state = SNTX_NUL;
        else                        // 适用于 return <expression>;
            syntax_state = SNTX_SP;
        syntax_indent();
    
        if (token != TK_SEMICOLON)
        {
            expression();
        }
        syntax_state = SNTX_LF_HT;
        skip(TK_SEMICOLON);
    }

    3.3 表达式语法分析

    语法定义:

    <表达式>::=<赋值表达式>{<逗号><赋值表达式>}
    
    <相等类表达式>::=<关系表达式>{<等于号><关系表达式>|<不等于号><关系表达式>}
    
    <关系表达式>::=<加减类表达式>{
                <小于号><加减类表达式>
                |<大于号><加减类表达式>
                |<小于等于号><加减类表达式>
                |<大于等于号><加减类表达式>}
    
    <加减类表达式>::=<乘除类表达式>{
                <加号><乘除类表达式>
                <减号><乘除类表达式>}
    
    <乘除类表达式>::=<一元表达式>{
                <星号><一元表达式>
                |<除号><一元表达式>
                |<取余运算符><一元表达式>}
    
    <一元表达式>::=<后缀表达式>
                |<与号><一元表达式>
                |<星号><一元表达式>
                |<加号><一元表达式>
                |<减号><一元表达式>
                |<sizeof表达式>
    <sizeof表达式>::=<sizeof关键字>(<类型区分符>)
    
    <后缀表达式>::=<初等表达式>{
                <左中括号><expression><右中括号>
                |<左小括号><右小括号>
                |<左小括号><实参表达式表><右小括号>
                |<点号>IDENTIFIER
                |<箭头>IDENTIFIER}
    <实参表达式表>::=<赋值表达式>{<逗号><赋值表达式>}
    
    <初等表达式>::=<标识符>|<整数常量>|<字符串常量>|<字符常量>|(<表达式>)

    3.3.1 表达式

    表达式的语法图:
    这里写图片描述
    表达式的代码和语法:

    /***********************************************************
    * 功能:   解析表达式
    *
    * <expression>::=<assignment_expression>{<TK_COMMA><assignment_expression>}
    **********************************************************/
    void expression()
    {
        while (1)
        {
            assignment_expression();
            if (token != TK_COMMA)
                break;
            get_token();
        }
    }

    3.3.2 赋值表达式

    赋值表达式的语法图:
    这里写图片描述
    赋值表达式的代码和语法:

    /***********************************************************
    * 功能:   解析赋值表达式
    *
    * <assignment_expression>::= <equality_expression>
    *       |<unary_expression><TK_ASSIGN> <equality_expression>
    *
    *非等价变换后文法:
    * <assignment_expression>::= <equality_expression>
    *       {<TK_ASSIGN><assignment_expression>}
    **********************************************************/
    void assignment_expression()
    {
        equality_expression();
        if (token == TK_ASSIGN)
        {
            get_token();
            assignment_expression();
        }
    }

    3.3.3 相等类表达式

    相等类表达式的语法图:
    这里写图片描述
    相等类表达式的代码和语法:

    /***********************************************************
    * 功能:   解析相等类表达式
    *
    * < equality_expression >::=<relational_expression>
    *       {<TK_EQ> <relational_expression>
    *       |<TK_NEQ><relational_expression>}
    **********************************************************/
    void equality_expression()
    {
    
        int t;
        relational_expression();
        while (token == TK_EQ || token == TK_NEQ)
        {
            t = token;
            get_token();
            relational_expression();
        }
    }

    3.3.4 关系表达式

    关系表达式的语法图:
    这里写图片描述
    关系表达式的代码和语法:

    /***********************************************************
    * 功能:   解析关系表达式
    *
    * <relational_expression>::=<additive_expression>{
    *       <TK_LT><additive_expression>
    *       |<TK_GT><additive_expression>
    *       |<TK_LEQ><additive_expression>
    *       |<TK_GEQ><additive_expression>}
    **********************************************************/
    void relational_expression()
    {
        additive_expression();
        while ((token == TK_LT || token == TK_LEQ) ||
            token == TK_GT || token == TK_GEQ)
        {
            get_token();
            additive_expression();
        }
    }

    3.3.5 加减类表达式

    加减类表达式的语法图:
    这里写图片描述
    加减类表达式的代码和语法:

    /***********************************************************
    * 功能:   解析加减类表达式
    *
    * <additive_expression>::=< multiplicative_expression>
    *       {<TK_PLUS> <multiplicative_expression>
    *       <TK_MINUS>< multiplicative_expression>}
    **********************************************************/
    void additive_expression()
    {
        multiplicative_expression();
        while (token == TK_PLUS || token == TK_MINUS)
        {
            get_token();
            multiplicative_expression();
        }
    }

    3.3.6 乘除类表达式

    乘除表达式的语法图:
    这里写图片描述
    乘除类表达式的代码和语法:

    /***********************************************************
    * 功能:   解析乘除类表达式
    *
    * <multiplicative_expression>::=<unary_expression>
    *       {<TK_STAR>  < unary_expression >
    *       |<TK_DIVIDE>< unary_expression >
    *       |<TK_MOD>  < unary_expression >}
    **********************************************************/
    void multiplicative_expression()
    {
        int t;
        unary_expression();
        while (token == TK_STAR || token == TK_DIVIDE || token == TK_MOD)
        {
            t = token;
            get_token();
            unary_expression();
        }
    }

    3.3.6 一元表达式

    一元表达式的语法图:
    这里写图片描述
    一元表达式的代码和语法:

    /***********************************************************
    * 功能:   解析一元表达式
    *
    * <unary_expression>::= <postfix_expression>
    *           |<TK_AND><unary_expression>
    *           |<TK_STAR><unary_expression>
    *           |<TK_PLUS><unary_expression>
    *           |<TK_MINUS><unary_expression>
    *           |<KW_SIZEOF><TK_OPENPA><type_specifier><TK_ CLOSEPA>
    **********************************************************/
    void unary_expression()
    {
        switch (token)
        {
        case TK_AND:
            get_token();
            unary_expression();
            break;
        case TK_STAR:
            get_token();
            unary_expression();
            break;
        case TK_PLUS:
            get_token();
            unary_expression();
            break;
        case TK_MINUS:
            get_token();
            unary_expression();
            break;
        case KW_SIZEOF:
            sizeof_expression();
            break;
        default:
            postfix_expression();
            break;
        }
    }
    3.3.6.1 sizeof表达式

    sizeof表达式的语法图:
    这里写图片描述
    sizeof表达式的代码和语法:

    /***********************************************************
    * 功能:   解析sizeof表达式
    *
    * <sizeof_expression>::=
    *       <KW_SIZEOF><TK_OPENPA><type_specifier><TK_ CLOSEPA>
    **********************************************************/
    void sizeof_expression()
    {
        get_token();
        skip(TK_OPENPA);
        type_specifier();
        skip(TK_CLOSEPA);
    }

    3.3.7 后缀表达式

    后缀表达式的语法图:
    这里写图片描述
    后缀表达式的代码和语法:

    /***********************************************************
    * 功能:   解析后缀表达式
    *
    * <postfix_expression>::=  <primary_expression>
    *       {<TK_OPENBR><expression> <TK_CLOSEBR>
    *       |<TK_OPENPA><TK_CLOSEPA>
    *       |<TK_OPENPA><argument_expression_list><TK_CLOSEPA>
    *       |<TK_DOT><IDENTIFIER>
    *       |<TK_POINTSTO><IDENTIFIER>}
    **********************************************************/
    void postfix_expression()
    {
        primary_expression();
        while (1)
        {
            if (token == TK_DOT || token == TK_POINTSTO)
            {
                get_token();
                token |= SC_MEMBER;
                get_token();
            }
            else if (token == TK_OPENBR)
            {
                get_token();
                expression();
                skip(TK_CLOSEBR);
            }
            else if (token == TK_OPENPA)
            {
                argument_expression_list();
            }
            else
                break;
        }
    }
    3.3.7.1 实参表达式

    实参表达式的语法图:
    这里写图片描述
    实参表达式的代码和语法:

    /***********************************************************
    * 功能:   解析实参表达式表
    *
    * <argument_expression_list >::=<assignment_expression>
    *       {<TK_COMMA> <assignment_expression>}
    **********************************************************/
    void argument_expression_list()
    {
        get_token();
        if (token != TK_CLOSEPA)
        {
            for (;;)
            {
                assignment_expression();
                if (token == TK_CLOSEPA)
                    break;
                skip(TK_COMMA);
            }
        }
        skip(TK_CLOSEPA);
        // return value
    }

    3.3.8 初等表达式

    初等表达式的语法图:
    这里写图片描述
    初等表达式的代码和语法:

    /***********************************************************
    * 功能:   解析初等表达式
    *
    * <primary_expression>::=<IDENTIFIER>
    *       |<TK_CINT>
    *       |<TK_CSTR>
    *       |<TK_CCHAR>
    *       |<TK_OPENPA><expression><TK_CLOSEPA>
    **********************************************************/
    void primary_expression()
    {
        int t;
        switch (token)
        {
        case TK_CINT:
        case TK_CCHAR:
            get_token();
            break;
        case TK_CSTR:
            get_token();
            break;
        case TK_OPENPA:
            get_token();
            expression();
            skip(TK_CLOSEPA);
            break;
        default:
            t = token;
            get_token();
            if (t < TK_IDENT)
                expect("标识符或常量");
            break;
        }
    }

    四、执行结果

    主程序入口为main.c:

    int main(int argc, char ** argv)
    {
    
        fin = fopen("./test.c", "rb");
        system("pause");
        if (!fin)
        {
            printf("不能打开SC源文件!\n");
            return 0;
        }
        init();
        getch();
        get_token();
        translation_unit();
        cleanup();
        fclose(fin);
        printf("%s 语法分析成功!", argv[1]);
        system("pause");
        return 1;
    }

    对没有缩进的test.c源文件进行语法分析
    test.c:

    /*********************************************************** 
     * test.c
     **********************************************************/
    struct point{int x;  int y;};
    void main()
    {int arr[10]; int i;    struct point pt;
    pt.x =1024;pt.y=768;
    for(i = 0; i < 10; i = i + 1)   {arr[i]=i;          
    if(i == 6){continue;        }
    else{printf("arr[%d]=%d\n",i,arr[i]);}}
    printf("pt.x = %d, pt.y = %d\n",pt.x,pt.y);}

    可以得到:
    这里写图片描述

    展开全文
  • 语法分析

    2018-04-24 23:29:35
    语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。1、语法分析语法分析器的工作本质上就是按文法的产生式,识别输入符号串是否为一个...

    语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。

    1、语法分析器

    语法分析器的工作本质上就是按文法的产生式,识别输入符号串是否为一个句子。

    判断方法:自上而下的分析、自下而上的规约

    本章主要介绍自上而下分析法。

    2、自上而下分析

    自上而下分析的主旨是对任何输入串,试图用一切可能的办法,从文法开始符号(根结)出发,自上而下的为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。

    自上而下分析面临的问题:

    1、文法的左递归问题。2、回溯的不确定性,要求我们将已经完成工作推倒从来。3、虚假匹配的问题。4、不能准确地确定输入串中出错的位置。5、效率低。

    3、LL(1) 分析法

    【1】(消除直接左递归的方法

    设有产生式:P→Pα1|Pα2|…|Pαm|β1|β2|…|βn,其中每个βi不以P开头,每个αi不为ε

    消除P的直接左递归性就是把这些规则改写成:  P→β1P’|β2P’|…|βnP’      P’→α1P’| α2P’|…|αmP’| ε

    【2】(消除间接左递归的方法

    (1) 将间接左递归改造为直接左递归。将文法中所有如下形式的产生式:
                Pi →Pjγ|β1|β2|…|βn             Pj→δ1|δ2|δ3|…|δk

                改写成:  Pi →δ1γ|δ2γ|δ3γ|…|δkγ|β1|β2|…|βn

    (2)消除直接左递归

        P→ β1P'| β2P'|...| βnP'       P'→ α1 P'| α2 P'|...|αm P'| ε

    (3)化简改写后的文法,即去除那些从开始符号出发却永远无法到达的非终结符的产生规则。

    【3】(消除回溯

    定义FIRST集:令文法G是不含左递归的文法,对G的非终结符的候选α,定义它的开始符号(终结首符)集合:

        
    特别地,如果α=》ε,则ε∈FIRST(α)。

    如果非终结符A的任意两个候选式αi和αj的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ,则A可以根据所面临的第一个输入符号,准确地指派一个候选式α去执行任务,α是那个FIRST集含a的候选式,即  a ∈FIRST(α)。

    提取公共左因子:

    假设A的产生式为:A→δβ1|δβ2||δβn|γ1| γ2||γm,其中每个γ不以δ开头,那么把这些产生式改写为:  A→δA’ |γ1| γ2||γm         A’→β1|β2||βn。

    反复提取左因子(包括对新引进的非终结符,例如A)。

    【4】(FOLLOW集

    对文法G的任何非终结符A,定义它的后继符号集合:



    特别地,如果S=*》…A,则#∈FOLLOW(A)。

    FOLLOW(A)集合是所有句型中出现在紧接A之后的终结符号或#所组成的集合。

    当非终结符A面临输入符号a,且a不属于A的任意候选式的FIRST集但A的某个候选式的FIRST集包含ε时,只有当a ∈FOLLOW(A),才可能允许A自动匹配。

    【5】(不带回溯的自上而下分析的文法条件(LL(1)文法)
    (1)文法不含左递归。
    (2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即,若
    A→α1|α2|…|αn
    FIRST(αi)∩FIRST(αj)=Φ (i≠j)。
    (3)对于文法中的每个非终结符A,若它的某个候选首符集包含ε,则
    FIRST(A)∩FOLLOW(A)=Φ

    如果一个文法G满足以上条件,则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串,第2个L代表最左推导,1表示分析时每一步只看1个符号)。

    4、递归下降分析程序构造

    当一个文法满足LL(1)条件时,我们就可以构造一个不带回溯的自上而下分析程序,这个分析程序由一组(可能的)递归程序组成,每个过程对应文法的一个非终结符。这样一个分析程序称为递归下降分析器。

    具体做法:对文法的每一个非终结符都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时,就调用该非终结符的分析程序。

    5、预测分析程序

    预测分析表的构造:

    1.     FIRST(X)
    1)若X终结符,则FIRST(X)={X}
    2)若X为非终结符,且有X->a …的产生式,则把a加入到FIRST(X)中;
    3)若X->Y…是一个产生式,且Y为非终结符,则把FIRST (Y)-ε加入到FIRST(X)中;
    若X->Y1Y2Y3….YK,是产生式, Y1Y2Y3….Yi-1是非终结符,而且ε属于 FIRST (Yj)(1<=j<=i-1),则把FIRST (Yj)-ε加入到FIRST(X)中;如果ε属于所有的FIRST(Yj),则ε加入到FIRST(X)中
    2.     FOLLOW(X)
    1)对于文法的开始符,置#于FOLLOW(S)中
    2)若A->αBβ, 则把FIRST (β)-ε加入到FOLLOW(B)中,
    3)若A->αB 是一个产生式,或 A->αBβ是一个产生式,而β-> ε,则把FOLLOW(A)加入到FOLLOW(B)中
    3.     预测分析表的构造
    对文法G的每个产生式, A->α,进行下面的处理
    1)对每个终结符a,如果a属于FIRST(α),则把该产生式写入到M[A,a]
    2) 若ε属于FIRST(α),则对任何b属于FOLLOW(A), 把该产生式加入到M[A,b]
    3)所有无定义的M[A,a]标上出错标志

    结论:一个文法G的预测分析表不含多重入口,当且仅当该文法是LL(1)

    6、错误恢复

    跳过输入串中的一些符号,直到遇到同步符号。遇到同步符号时,将符号栈顶的非终结符出栈。将FOLLOW(A)设为同步符号。将FIRST(A)加入到同步符号。如果非终结符产生空串,可以自动匹配,以推迟检测到错误的时间。如果栈顶是终结符,当出错时,直接将栈顶出栈。

    课后习题:




    小结:

    每一章在最后反思的时候总会发现自己在学习中存在的不足。这一章题目中的知识点集中在求FIRST集,FOLLOW集以及预测分析表,虽然有关知识学到了,但是真正到自己运用来做题的时候还是有些“坎坷”,这也是对知识掌握不熟练的表现。虽然对这一章进行了总结,但是还要抽一些时间再看回顾一下所学知识。



    展开全文
  • 编译原理:语法分析

    万次阅读 多人点赞 2019-05-05 18:03:59
    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析器所提供的单词序列进行语法检测和结构分析...
  • 第四章——语法分析

    2018-04-22 22:58:35
    语法分析器的功能:语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。LL(1) 分析法:LL:L:left-&gt;right扫描;L:最左推导。消除...
  • 语法分析(一)

    2020-07-05 16:21:53
    算符优先分析法,LR分析法 从树叶节点开始构造语法树 归约:右部替换为左部符号 自上而下 递归下降分析法,预测分析程序 从根节点开始构造语法树 推导:左部替换为右部符号 问题:回溯(多个产生式候选)...
  • 编译原理 —— 什么是语法分析

    千次阅读 2019-05-06 14:44:24
    语法分析 识别句子中的各个短语 从词法分析器输出的token序列中识别出各类短语,并构造语法分析树(parse tree) 语法分析要解决的问题是:如何根据语法规则为输入句子构造语法分析树 转载地址: ...
  • 编译原理实验:自上而下语法分析

    千次阅读 2020-07-06 09:45:18
    编译原理实验报告:自上而下语法分析1. 实验题目:自上而下语法分析实验目的实验内容实验要求输入输出2. 设计思想3. 算法流程4. 源程序新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入...
  • 词法分析、语法分析、语义分析

    千次阅读 2018-05-30 13:11:24
    这里就是拿翻译句子来举例子,从英语翻译到汉语,我们需要分析句子的语义,要划分句子的成分要想进行语义分析就要划分句子成分,比如说划分为人、铁锤、窗户等等我们要想划分句子当中的各类成分,就要用语法分析来...
  • 词法分析(Lexical analysis或Scanning)和词法分析程序(Lexical analyzer或Scanner)  词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成...语法分析(Synta
  • 编译原理学习(三)--语法分析

    万次阅读 2012-05-07 10:55:27
    语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程。在具体理解语法分析树之前需要先理清楚一些基本概念: ①.产生式 用变量expr来表示表达式,用变量stmt表示语句,那么这个构造规则...
  • 首先注意一点:无论是那种语法分析,语法都是从左至右的读入符号!  自底向上分析法,也称移进-归约分析法。 它的实现思想是对输入符号串自左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,...
  • Redy语法分析--抽象语法树简介

    万次阅读 2014-07-27 12:52:24
     抽象语法树简介 (一)简介 抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上...抽象语法树并不依赖于源语言的语法,也就是说语法分析阶段所采用的上下文无文文法,因为在写文
  • https://gitee.com/wukangio/helison.archer 参上!
  • 依存分析:中文依存句法分析简介

    万次阅读 多人点赞 2018-05-09 11:13:10
    另一方面是句法分析技术,即根据给定的语法体系,自动推导出句子的句法结构,分析句子所包含的句法单位和这些句法单位之间的关系。 二、语法体系 句法分析需要遵循某一语法体系,根据该体系
  • LL语法分析器和LR语法分析器的比较

    千次阅读 2014-06-10 18:18:04
    最近正在读久负盛名的“龙书”,
  • 词法分析,语法分析,语义分析,构造执行树,生成执行计划,计划的执行。 Mysql 并没有使用lex来实现词法分析,但是语法分析却用了yacc。 与之对比的Sqlite3数据库,SQLite的词法分析器是手工写的,语法分析器...
  •  练习构造递归下降语法分析程序的方法,熟悉上下文无关文法的使用,加深对课堂教学的理解;提高语法分析方法的实践能力 【实验要求】  利用某一高级程序设计语言构造语法分析程序  【具体要求】对于给定的文法...
  • 【软考】-词法分析、语法分析、语义分析、

    千次阅读 热门讨论 2018-10-01 10:33:57
    前两天串这一部分内容的时候,对于词法分析,语法分析,语义分析这三项不是很熟悉,所以就简单总结下,希望能够帮助理解;
1 2 3 4 5 ... 20
收藏数 481,703
精华内容 192,681
关键字:

语法分析