语法_语法分析器 - CSDN
  • 完整的词法、语法、语义程序源代码+实验报告(实现过程),参照蒋立源的《编译原理》
  • 语法制导的翻译

    万次阅读 多人点赞 2017-12-01 10:05:21
    继词法分析和文法分析之后,本文将介绍使用上下文无关文法来引导对语言的翻译,包括SDD和SDT。

    继词法分析和文法分析之后,本文将介绍使用上下文无关文法来引导对语言的翻译。

    SDD

    语法制导定义(Syntax-Directed Definition,SDD)是一个上下文无关文法和属性及语义规则的结合。属性和文法符号相关联,语义规则和产生式相关联,文法符号X的属性a表示为X.a。

    非终结符号可以有两种属性:

    • 综合属性:如果语法分析树上的结点N的某个属性a只能通过N的子结点和N本身的属性值来定义,那么属性a是结点N的一个综合属性;
    • 继承属性:如果语法分析树上的结点N的某个属性b只能通过N的父结点、N本身和N的兄弟结点的属性值来定义,那么属性a是结点N的一个继承属性。

    终结符号可以有综合属性,但不能有继承属性,终结符号的属性是由词法分析器提供的词法值。

    综合属性

    如果语法分析树中的结点N的某个属性a只能通过N的子结点或N本身的属性值来定义,那么属性a是结点N的一个综合属性。

    对表达式文法G:

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

    它对应的SDD如下:

    20171122_img1

    其中,属性val是文法符号的数值,属性lexval是由词法分析器返回的数值。为id1*id2+id3构建语法分析树,其中,id1、id2、id3的lexval属性分别为3、4、5:

    20171122_img2

    在这棵语法分析树中,所有结点的属性都被显示了出来,这样的语法分析树也称为注释语法分析树

    继承属性

    如果语法分析树上的结点N的某个属性b只能通过N的父结点、N本身和N的兄弟结点的属性值来定义,那么属性a是结点N的一个继承属性。

    考虑上一小节中的表达式文法的非左递归形式G’:

        E → TE'
        E'→ +TE' | ε
        T → FT'
        T'→ *FT' | ε
        F → (E) | id

    它对应的SDD如下:

    20171122_img3

    其中,属性val是文法符号的数值,属性lexval是由词法分析器返回的数值,属性inh是一个继承属性,属性syn是一个综合属性。为id1*id2+id3构建语法分析树,其中,id1、id2、id3的lexval属性分别为3、4、5:

    20171122_img4

    在这棵语法分析树中,属性inh“向下地传递参数”,属性syn“向上地返回结果”,关于继承属性和综合属性的求值顺序将在下一小节介绍。

    SDD的求值顺序

    和终结符号的综合属性直接由词法分析器给出不同,非终结符号的综合属性和继承属性都或多或少地依赖于其他属性,因此确定一棵注释语法分析树中属性的求值顺序是十分重要的,依赖图可以帮助我们完成这个工作。

    依赖图描述了某个语法分析树中的属性实例之间的信息流,从一个属性实例到另一个属性实例的边表示计算第二个属性实例需要用到第一个属性实例的值。具体地讲,一个依赖图包括:

    • 属性结点:对于语法分析树中的每个结点N,N的每个属性在依赖图中都有一个结点;
    • 综合属性的边:如果和产生式p关联的语义规则通过X.a的值定义了综合属性Y.b的值,那么在依赖图中有一条从X.a到Y.b的边;
    • 继承属性的边:如果和产生式p关联的语义规则通过X.a的值定义了继承属性Y.b的值,那么在依赖图中有一条从X.a到Y.b的边。

    得到依赖图后,如果这个依赖图中没有环,那么这个依赖图至少存在一个拓扑排序。假设依赖图的结点集合为N,边集合为E,计算此依赖图的拓扑排序的步骤为:

    1. 构建一个序列A,A的长度为len(N),将i初始化为0;
    2. 从N中选出一个入度为0的结点n,从N中删除n且从E中删除所有以n为起点的边,将A[i]设为n,同时将i加1;
    3. 如果N不为空,重复步骤2,否则排序结束,得到拓扑序列A[0]、A[1]、…、A[len(N)-1]。

    考虑图1的注释语法分析树,它的依赖图如下,结点前的标号是拓扑排序后的结果:

    20171122_img5

    考虑图2的注释语法分析树,它的依赖图如下,结点前的标号是拓扑排序后的结果:

    20171122_img6

    到这里,我们已经知道了如何借助依赖图确定一棵注释语法分析树中属性的求值顺序。但是,不是所有的注释语法分析树都能通过依赖图找到一个拓扑排序,如果依赖图中存在环,那么这个依赖图没有拓扑排序。如果我们能小心地定义SDD中的语义规则使得其依赖图中没有环,那么我们一定能够确定此SDD中属性的求值顺序,下面介绍的S属性的SDD和L属性的SDD一定能确定属性的求值顺序。

    S属性的SDD

    如果一个SDD的每个属性都是综合属性,那么这个SDD是一个S属性的SDD。

    对于一个S属性的SDD,可以按照语法分析树结点的任何自底向上顺序来计算它的各个属性值。S属性的SDD可以在自底向上的语法分析过程中实现。

    L属性的SDD

    L属性的SDD的思想是在一个产生式体所关联的各个属性之间,依赖图的边总是从左到右,而不能从右到左。也就是说,每个属性必须满足如下条件:

    • 要么是一个综合属性;
    • 要么是一个继承属性,但是它的语义规则有这些限制:假设有产生式A→X1X2…Xn和继承属性Xi.a,Xi.a的计算规则只能使用A的继承属性以及Xj(1<=j<=i)的综合属性或继承属性,并且Xi的全部属性组成的依赖图中不存在环。

    L属性的SDD可以在自顶向下的语法分析过程中实现。

    SDT

    语法制导的翻译方案(Syntax-Directed Translation scheme,SDT)是SDD的一种补充,它是在其产生式体中嵌入程序片段的一个上下文无关文法,这些程序片段称为语义动作,它们可以出现在产生式体中的任何地方。通常情况下,语义动作的两边要加上花括号,如果花括号作为文法符号出现,则要给它们加上引号。

    实现SDT的通用方法

    语义动作可以放在产生式体中的任何位置,当一个语义动作左边的所有符号都被处理完后该动作立即执行。更具体的,对产生式A→X{a}Y,有:

    • 如果语法分析过程是自底向上的,那么当X出现在语法分析栈的栈顶时立即执行动作a;
    • 如果语法分析过程是自顶向下的,那么当试图展开Y(Y是非终结符号)或在输入中检测到Y(Y是终结符号)之前执行动作a。

    通用的SDT实现方法如下:

    1. 忽略语义动作,对输入进行语法分析,并产生一棵语法分析树;
    2. 然后检查每个内部结点N,假设它的产生式是A→α。将α中的各个动作当作N的附加子结点加入,使得N的子结点从左到右和α中的符号及动作完全一致;
    3. 对这棵语法分析树进行前序遍历,并且当访问到一个以某个动作为标号的结点时立即执行此动作。

    对于表1显示的SDD,把它转换成SDT:

    20171122_img7

    注意到,此SDT和相应的SDD相比,只有前两个产生式的语义动作和原来的语义规则不同。由于这两个产生式的产生式头已经是开始符号,因此相应的语义动作需要把实现结果输出。由此SDT构建的嵌入了动作的语法分析树如下:

    20171122_img8

    对上面的语法分析树进行前序遍历,每遇到一个动作就立即执行它,遍历完成后就实现了此SDT。

    在语法分析过程中实现SDT

    可以在语法分析过程中实现的SDT包括后缀SDT和L属性定义的SDT,后缀SDT通常在自底向上的语法分析过程中实现,L属性定义的SDT通常在自顶向下的语法分析过程中实现。注意,不是所有的SDT都能在语法分析过程中实现。

    后缀SDT

    如果一个SDD的基础文法是LR文法并且此SDD是S属性定义的,那么我们可以构造这样一个SDT,其中的每个动作都放在产生式的最后,并且在按照这个产生式将产生式体归约为产生式头的时候执行这个动作。像这样所有动作都在产生式体最右端的SDT也称为后缀翻译方案(后缀SDT)。

    将一个S属性定义的且基础文法为LR文法的SDD转换为一个SDT的规则如下:

    • 将计算一个产生式头的综合属性的动作放置在这个产生式体的最右端。

    注意到,由于表1中的SDD是S属性定义的且其基础文法G是LR文法,因此可以把它转换成后缀SDT,表3中的SDT就是此SDD的一个转换形式。下面我们进一步改进表3中的SDT,使其能够在语法分析过程中实现:

    20171122_img9

    表4中的stack表示LR语法分析栈,top指向栈顶。为了帮助读者理解这个SDT中的语义动作,以产生式F→(E)为例,考虑将(E)归约成F的过程,如图6所示:

    20171122_img10

    图6显示了把(E)归约成F的LR语法分析过程。图6(a)是即将把(E)归约成F的语法分析栈快照,此时有stack[top]=")"stack[top-1]="E"stack[top-2]="("。执行的归约动作是连续3次出栈操作(将”)”、”E”、”(“依次弹出栈顶,如图6(b))和1次入栈操作(将”F”压入栈顶,如图6(c))。注意到,(c)中的top相当于(a)中的top-2,也就是说,F实际上出现在(a)中的stack[top-2]处;另外,由于E.val将被赋值给F.val,并且E出现在(a)中的stack[top-1]处,因此在(a)中有stack[top-2].val=stack[top-1].val;将(a)变成(c)还需要执行2次出栈操作(实际上是3次出栈操作和1次入栈操作),因此还需要把top指针向下移动2位。

    从SDT中消除左递归

    在详细介绍如何在语法分析过程中实现L属性定义的SDT之前,我们先来介绍如何从SDT中消除左递归。在介绍语法分析的时候我们知道了带有左递归的文法不能按照自顶向下的方式进行语法分析,并且我们还知道如何从一个左递归的文法中消除左递归。当文法是SDT的一部分时,我们还需要考虑如何处理其中的语义动作。

    情况1

    最简单的情况是,我们只需要关心一个SDT中动作的执行顺序。在这种情况下,当对文法进行消除左递归的转换时,可以简单地将动作当成终结符号处理。之所以可以这样做,是因为对文法的转换保持了由文法生成的符号串中终结符号的顺序。举个例子,对下面的SDT:

        EE+T { print('+'); }
        E → T

    将动作看作终结符号,消除左递归后得到的SDT为:

        E → TR
        R → +T { print('+'); } R | ε
    情况2

    另一种比较复杂的情况是,一个SDT的动作包含了对属性值的计算。举个例子,对下面的SDT:

        A → A1Y { A.a = g(A1.a, Y.y); }
        A → X { A.a = f(X.x); }

    其中,f和g是两个任意的函数,对基础文法消除左递归得到:

        A → XR
        R → YR | ε

    现在尝试在文法中加入语义动作。我们给文法符号R附加上两个属性,一个属性i是继承属性,它用来保存函数f和g的结果,另一个属性s是综合属性,它会在计算结束后返回最终的计算结果。得到的SDT为:

        A → X { R.i = f(X.x); } R { A.a = R.s; }
        R → Y { R1.i = g(R.i, Y.y); } R1 { R.s = R1.s; }
        R → ε { R.s = R.i; }

    我们用注释语法分析树来展示对SDT消除左递归前后的变化(这里省略了对R.s的计算):

    20171122_img11

    L属性定义的SDT

    如果一个SDD的基础文法能够以自顶向下的方式进行语法分析,并且此SDD是L属性定义的,那么我们可以把这个SDD转换成一个L属性定义的SDT。

    将一个L属性定义的SDD转换为一个SDT的规则如下:

    • 将计算某个非终结符号A的继承属性的动作插入到产生式体中紧靠在A的本次出现之前的位置上。如果A的多个继承属性以无环的方式相互依赖,就需要对这些属性的求值动作进行排序,以便先计算需要的属性;
    • 将计算一个产生式头的综合属性的动作放置在这个产生式体的最右端。

    在语法分析过程中实现L属性定义的SDT的方法包括:

    1. 使用一个递归下降的语法分析器。它为每个非终结符号都建立一个函数,对应于非终结符号A的函数以参数的形式接受A的继承属性,并返回A的综合属性;
    2. 使用一个递归下降的语法分析器,以边扫描边生成的方式生成代码;
    3. 与LL语法分析器结合实现一个SDT。属性的值存放在语法分析栈中,各个规则从栈中的已知位置获取需要的属性值;
    4. 与LR语法分析器结合实现一个SDT。如果基础文法是LL的,我们总是可以按照自底向上的方式来处理语法分析和翻译过程。
    在递归下降语法分析过程中进行翻译

    一个递归下降的语法分析器对每个非终结符号A都有一个函数A,我们可以把这个语法分析器扩展为一个翻译器:

    1. 函数A的参数是非终结符号A的继承属性,返回值是非终结符号A的综合属性;
    2. 在函数A的函数体中进行语法分析并处理属性。

    举个例子,考虑表2中的SDD,非终结符号E对应的函数E如下:

    float E() {
        float Tval = T();
        float EQUOTEinh = Tval;
        float EQUOTEsyn = EQUOTE(EQUOTEinh);
        float Eval = EQUOTEsyn;
        return Eval;
    }

    在函数E中,首先,注意到函数E没有任何参数,这是因为非终结符号E没有任何继承属性;其次,在E的函数体中,调用了函数T和函数EQUOTE,前者对应于非终结符号T(T也没有任何继承属性),后者对应于非终结符号E’(E’有一个继承属性);最后,定义了一系列变量来保存继承属性或综合属性(实际上是为了方便读者理解才定义了如此多的变量),并返回了计算结果。

    另外,非终结符号E’对于的函数EQUOTE如下:

    float EQUOTE(float EQUOTEinh) {
        if (下一个输入符号为'+') {
            读取输入
            return EQUOTE(EQUOTEinh + T());
        } else if (输入已经结束) {
            return EQUOTEinh;
        } else {
            ...
        }
    }
    边扫描边生成代码

    对上面的例子,如果需要在调用函数EQUOTE的过程中打印出表达式,而不是返回最后的结果,那么可以一边扫描一边生成代码。使用这个方法需要满足的条件是:每个非终结符号存在一个综合属性作为主属性,对主属性的求值是将相关产生式体中的非终结符号的主属性值连接起来得到的(连接时也可能包括非主属性),各个非终结符号的主属性值在连接运算中出现的顺序和这些非终结符号在产生式体中出现的顺序相同。

    修改函数EQUOTE,使其打印出表达式:

    float EQUOTE(float EQUOTEinh) {
        if (下一个输入符号为'+') {
            读取输入
            print(EQUOTEinh);
            print('+');
            float Tval = T();
            return EQUOTE(EQUOTEinh + Tval);
        } else if (输入已经结束) {
            return EQUOTEinh;
        } else {
            ...
        }
    }
    L属性的SDD与LL语法分析

    对于一个基础文法是LL文法的L属性的SDD,如果我们已经把它转换成了一个L属性定义的SDT,那么我们可以在LL语法分析过程中完成对它的翻译。

    为了在LL语法分析过程中实现L属性定义的SDT,语法分析栈需要被扩展,扩展后的语法分析栈可以存放三种记录:

    • 代表终结符号和非终结符号的记录,实际上是状态记录;
    • 动作记录。非终结符号A的继承属性放在表示A的栈记录中,对A的继承属性求值的代码放在一个紧靠在A的栈记录之上的动作记录中;
    • 综合记录。非终结符号A的综合属性放在一个紧靠在A的栈记录之下的综合记录中。

    在语法分析过程中,某些属性值可能会被拷贝到动作记录或综合记录中,这是因为一个分析表驱动的LL语法分析器模拟了一个最左推导过程。举个例子,当语法分析器按照一个产生式A→BC对栈顶的非终结符号A展开时,栈顶的A被替换为BC,假设C有一个继承属性C.i依赖于A的某个属性,但是此时已经无法访问到A,因此我们需要把A的属性临时拷贝到C的动作记录中,这样一来,C在计算其属性C.i时就能找到这个依赖属性了。

    下图是用文法G’中的产生式E'→ +TE'对E’进行展开的语法分析过程:

    20171122_img12

    我们对这个语法分析过程进行分析:

    1. 图8(a)中展示了即将展开E'的语法分析栈,此时栈顶是E'的栈记录,紧跟其后的是E'的综合记录,假设E'.inh已经被拷贝给了E1'的动作记录中的EQUOTEval
    2. 图8(b)用产生式体+TE1'替换了E'。一开始,+的栈记录在栈顶,它将和输入进行匹配,在匹配完成后,它被弹出栈顶,T的栈记录变为栈顶;
    3. 由于T的栈记录位于栈顶,因此会用某个产生式对符号T进行展开,当这个展开过程结束后,T的综合记录将位于栈顶,并且该记录中的val属性值已经被赋值了;
    4. 由于E1'的继承属性依赖于T.val,因此在将T的综合记录弹出栈顶之前,还需要把T.val拷贝给E1'的动作记录中的Tval
    5. 此时E1'的动作记录位于栈顶,它使用两个拷贝的属性值计算E1'.inh,计算的结果被放入E1'的栈记录中;
    6. 由于E1'的栈记录位于栈顶,因此会用某个产生式对符号E1'进行展开,当这个展开过程结束后,E1'的综合记录将位于栈顶,并且该记录中的syn属性值已经被赋值了;
    7. E1'的综合记录将E1'.syn赋值给E'.syn,到这里,用产生式体+TE1'展开E'的过程结束。
    L属性的SDD与LR语法分析

    我们可以使用自底向上的方法来完成任何可以用自顶向下方式完成的翻译过程,也就是说,对一个基础文法为LL文法的L属性的SDD,我们可以修改这个文法,使得可以在LR语法分析过程中实现这个新文法上的SDD。具体的方法包括:

    1. 将给定的基础文法为LL文法的L属性的SDD转换成SDT,这样的SDT在每个非终结符号之前放置语义动作计算它的继承属性,并且在产生式最右端放置一个语义动作计算综合属性;
    2. 对每个内嵌的语义动作,向这个文法中引入一个标记非终结符号来替换它。每个这样的位置都有一个不同的标记,并且对于任意一个标记M都有一个产生式M→ε;
    3. 如果标记非终结符号M在某个产生式A→α{a}β中替换了语义动作a,对a进行修改得到a’,并且将a’关联到M→ε上。这个动作a’将动作a需要的A或α中符号的任何属性作为M的继承属性进行拷贝,并且按照a中的方法计算各个属性,计算得到的属性将作为M的综合属性。

    对表2中的SDD,先将其转换成SDT:

    20171122_img13

    以这个SDT中的产生式E'→+TE1'为例,它的LR语法分析过程如下:

    20171122_img14

    图9(a)中首先对产生式E'→+TE1'进行变换,引入了一个标记非终结符号M对嵌入的动作{E1'.inh=E'.inh+T.val}进行替换,其中,E'.inhT.val将作为M的两个继承属性,E1'.inh将作为M的综合属性。

    图9(b)中是LR语法分析栈,我们假设接下来的输入能够匹配产生式体+TME1'并且最终被归约成产生式头E'。在这个语法分析栈中,我们不知道栈顶的记录代表了哪一个文法符号(或者状态),但是我们一定能确定这个记录中的某个字段保存了E’的inh属性。

    图9(c)中显示了即将把产生式体+TME1'归约成产生式头E'之前的语法分析栈。我们对从图9(b)到图9(c)的LR语法分析过程进行详细的分析:

    1. 语法分析栈的初始状态如图9(b)所示,此时栈顶的记录保存了E’的inh属性;
    2. 由于检测到的下一个输入的文法符号是”+”,因此识别出的产生式肯定是E'→+TME1'
    3. 假设接下来的输入被成功归约成T,此时栈顶是代表非终结符号T的记录,该记录中保存了T的val属性。由于我们已经确定了产生式是E'→+TME1',因此我们可以确定下一步是把ε归约成M;
    4. 在把ε归约成M时,栈顶是代表标记非终结符号M的记录,并且会执行一个动作,这个动作把E.inh(位于stack[top-3]的记录中)和T.val(位于stack[top-1]的记录中)分别拷贝给M的i和j属性,同时使用属性i和j计算它的综合属性s,属性s实际上是下一个非终结符号E1’的继承属性;
    5. 假设接下来的输入被成功归约成E1’,此时栈顶是代表非终结符号E1’的记录,计算E1’的syn属性时用到的E1’的inh属性是从代表M的记录中拿到的,这种情况下,代表M的记录相当于图9(b)中栈顶的记录,唯一的区别是这里我们能够知道保存E1’.inh的记录是代表M的记录;
    6. 由于句柄+TME1'已经位于栈顶,因此我们可以把+TME1'归约成E',此时会执行一个动作,这个动作把E1’.syn拷贝到stack[top-3]记录中,并执行3次出栈操作(实际上是4次出栈操作和1次入栈操作)。到这里,从图9(b)到图9(c)的LR语法分析过程结束。

    fightingZh
    欢迎关注微信公众号fightingZh٩(๑>◡<๑)۶

    展开全文
  • 语法分析 一、语言与文法 程序设计语言与自然语言有一个重要的区别,程序设计语言需要把语言的三个基本要素设计出来:语法、语义、语用;但是在自然语言叙述的时候只需要通话双方可以相互理解即可。 (程序设计语言...

    语法分析

    一、语言与文法

    1. 程序设计语言与自然语言有一个重要的区别,程序设计语言需要把语言的三个基本要素设计出来:语法、语义、语用;但是在自然语言叙述的时候只需要通话双方可以相互理解即可。
      (程序设计语言必须清晰)
    2. 那么为什么要定义文法呢?为什么没有直接讨论语法?
      语法的形式化表达方式——文法,在程序设计中需要将语言使用形式化的方式来表达,用程序解决问题的时候需要使用比较规范的形式描述出来才容易实现。(目的就是清楚的描述问题)
      也就是说文法是语法的一种载体,通过文法的规则来描述实际上的语法
      通俗说法就是把类似主谓宾定状补的规则转化为程序可以直接表示的内容。
      在这里插入图片描述
      文法相当于在词法分析器中的DFA和NFA,可以通过构造出一个语法分析器来检查输入的字符串是否满足相应的语法规则。

    二、文法的表示形式

    2.1 巴克斯范式BNF(实际上不使用)

    在这里插入图片描述
    定义了一个赋值语句的形式,变量 赋值号 表达式,这种形式还可以继续定义,这里只是几条规则,定义一个文法应该是规则的集合

    2.2上下文无关文法(实际使用方法)

    在这里插入图片描述
    实际采用的文法规则,和上面的BNF是等价的
    在这里插入图片描述


    终极符和非终极符
    1. 终极符和非终极符的理解
    非终极符:可以进行继续推导产生非终极符或终极符或二者的组合的串,可以理解为尚能继续分解成更小元素的串
    终极符:最小的不可再分的串
    

    ⚠️开始的元素必须来自非终极符集合

    1. 终极符和非终极符的出现位置
      VT终极符集合,只能出现在规则的右部(不能继续推导)
      VN非终极符集合,在语法规则中出现在规则的左部,也可以出现在右部

    在这里插入图片描述
    例子:

    如果把N看成是开始符,则有:
    N->ND(N->ND)
     ->N0(D->0)
     ->D0(N->D)
     ->80(D->8终止)
     这样利用上面P中的规则对N进行处理的到的最终全部状态都是终极符中的串即终止运行
    

    基本概念

    在这里插入图片描述
    直接推导就是直接一个表达式就可以解决的问题。
    +:一步或者多步/ *:零步或多步
    在这里插入图片描述

    • 从开始符开始推导出来的所有串都是该文法的句型,一个串里面可以有非终极符也可以有终极符。
    • 句子一定是从开始符推导出来的,但是如果是句子其中就只能含有终极符,不能再继续推导。

    ⚠️从词法分析中生成的token都是终极符,非终极符是文法再生成的,语言即符合文法规则的句子集合

    三、基本概念与高级语言语法

    1. 每一种高级程序设计语言都有自己的语法
    2. 符合高级语言文法的程序就是该语法的句子
    3. 所有程序组成的集合就构成了语言

    所谓的句子就是用户写的程序,即每个人写的程序,如果符合文法的话就应该是文法的一个句子。
    在这里插入图片描述
    每一个<>中的内容都可以就行向下定义,一直定义到终极符的级别。


    3.1验证程序是不是语法的句子

    在这里插入图片描述
    使用右部替换左部称为推导,使用左部替换右部称为归约。
    ⚠️剪枝的方法是经常使用的!

    为了进行自底向上的语法分析给出的定义,必须找出规则的右部,然后使用规则的左部去替换,但是一个串中出现了一个规则的右部不一定可以直接使用左部来进行替换

    为了使用自底向上的方法引出的相关概念:

    在这里插入图片描述
    相关概念理解:

    1. 短语的概念建立在句型之上(同一个字符串,如果句型变了,之前是短语可能后来就不是了)在一个句型里面,我们要找出一个串β,它是由前面的某一个非终极符推导出来的串,则这个串就可以叫做当前句型的短语(就是由某一个非终极符推导出来的)。
    2. 简单短语直接推导一次得到,短语>=1次。
    3. 句柄属于特殊的简单短语,在句型中短语可能有多个,最左边的这个就称作是句柄(⚠️句柄是简单短语)。

    句柄存在的背景:一个句型中可能有大量的简单短语,我们程序处理一个串不会到中间去截取,我们都是从左到右的扫描,我们从左往右扫找到第一个简单短语就进行归约,然后再找,所以说这种情形通常是为了处理的方便,从最左边找,找第一个

    1. 找句柄的相关问题
      a/ 找句柄归约实际上是最右推导的逆过程。在一个句型中,任何一个简单短语都可以规约成非终极符,找到β就可以把它归约成非终极符。
      b/给出了这个分析,实际上自底向上的语法分析方法就是一个找句柄的方法,不同的语法分析方法就是找句柄的方法不同,你给出一个新的找句柄的方法就是给了一个新的语法分析方法。
    二义性
    E->E+T|E*T|T
    如果这样写在计算E+E*T的时候先计算乘法和加法都是可以的,出现歧义
    涉及到运算的优先级和结合度的问题
    如果按照下面的方法写文法规则的话,暗含了先计算乘法,因为乘法的T是需要先解出再带入到上面的E->E+T|T中的。
    

    在这里插入图片描述

    分析步骤:
    1. 首先从开始符E开始
    2. 利用所给的所有规则,先熟悉所给的可能是文法的句型的串,看用现有的规则如何从外向内,或者从内向外构造可以尽可能的构造出当前想要判断是否是文法的句型的串
    

    从开始符出发进行推导的过程:
    在这里插入图片描述
    在这里插入图片描述

    3.2 基本概念

    1. 程序设计语言的语法中有递归是必然的,因为如果没有递归的话,句子的集合是一个有限的集合,而实际上一个语言的程序是无穷多的,主要是靠递归的形式控制的,但是递归程序一定有一个递归出口。
    2. 给出右递归是因为有的时候需要把一些左递归消除,但是不可能把递归彻底消除(不同于递归和循环的转换,而是使用两种递归的结合是把原来的式子变成不是左递归的形式)
      在这里插入图片描述

    相关解释:

    1. 带有“直接”字样的都是使用一步推导可以得到的
    2. 递归就是推导出来句子还含有左部的内容
      在这里插入图片描述

    相关解释:

    1. 注意对于句型和句子的区分,句子必须是终止符
    2. 关于推导,在自底向上的方法中,按照句柄的方式处理是比较好的,都是归约的过程,推导的时候也有同样的问题,一个句型中可能有很多的非终止符,那么下一步推导的过程中就有一个选择的问题,选择哪一个终止符进行下一步推导,先推导谁后推导谁。
    3. 最右推导也叫规范推导,最右推导也是找句柄的语法分析方法的逆过程。在这里插入图片描述
    展开全文
  • 在自然语言学习过程中,每个人一定都学过语法,例如句子可以用主语、谓语、宾语来表示。在自然语言的处理过程中,有许多应用场景都需要考虑句子的语法,因此研究语法解析变得非常重要。语法解析有两个主要的问题,其...

    什么是语法解析?

    在自然语言学习过程中,每个人一定都学过语法,例如句子可以用主语、谓语、宾语来表示。在自然语言的处理过程中,有许多应用场景都需要考虑句子的语法,因此研究语法解析变得非常重要。

    语法解析有两个主要的问题,其一是句子语法在计算机中的表达与存储方法,以及语料数据集;其二是语法解析的算法。

    对于第一个问题,我们可以用树状结构图来表示,如下图所示,S表示句子;NP、VP、PP是名词、动词、介词短语(短语级别);N、V、P分别是名词、动词、介词。


    实际存储的时候上述的树可以表示为(S (NP (N Boeing)) (VP (V is) (VP (V located) (PP (P in) (NP (N Seattle))))))。互联网上已经有成熟的、手工标注的语料数据集,例如The Penn Treebank Project (Penn Treebank II Constituent Tags)。

    对于第二个问题,我们需要有合适的算法来处理。这也是我们本章将要讨论的内容。

    上下文无关语法(Context-Free Grammer)

    为了生成句子的语法树,我们可以定义如下的一套上下文无关语法。
    1)N表示一组非叶子节点的标注,例如{S、NP、VP、N...}
    2)Σ表示一组叶子结点的标注,例如{boeing、is...}
    3)R表示一组规则,每条规则可以表示为X->Y1Y2...Yn,X∈N,Yi∈(N∪Σ)
    4)S表示语法树开始的标注

    举例来说,语法的一个语法子集可以表示为下图所示。当给定一个句子时,我们便可以按照从左到右的顺序来解析语法。例如,句子the man sleeps就可以表示为(S (NP (DT the) (NN man)) (VP sleeps))。


    这种上下文无关的语法可以很容易的推导出一个句子的语法结构,但是缺点是推导出的结构可能存在二义性。例如下面两张图中的语法树都可以表示同一个句子。常见的二义性问题有:1)单词的不同词性,如can一般表示“可以”这个情态动词,有时表示罐子;2)介词短语的作用范围,如VP PP PP这样的结构,第二个介词短语可能形容VP,也可能形容第一个PP;3)连续的名字,如NN NN NN。
      

    概率分布的上下文无关语法(Probabilistic Context-Free Grammar)

    由于语法的解析存在二义性,我们就需要找到一种方法从多种可能的语法树种找出最可能的一棵树。一种常见的方法既是PCFG (Probabilistic Context-Free Grammar)。如下图所示,除了常规的语法规则以外,我们还对每一条规则赋予了一个概率。对于每一棵生成的语法树,我们将其中所以规则的概率的乘积作为语法树的出现概率。


    综上所述,当我们或得多颗语法树时,我们可以分别计算每颗语法树的概率p(t),出现概率最大的那颗语法树就是我们希望得到的结果,即arg max p(t)。

    训练算法

    我们已经定义了语法解析的算法,而这个算法依赖于CFG中对于N、Σ、R、S的定义以及PCFG中的p(x)。上文中我们提到了Penn Treebank通过手工的方法已经提供了一个非常大的语料数据集,我们的任务就是从语料库中训练出PCFG所需要的参数。
    1)统计出语料库中所有的N与Σ;
    2)利用语料库中的所有规则作为R;
    3)针对每个规则A -> B,从语料库中估算p(x) = p(A -> B) / p(A);

    在CFG的定义的基础上,我们重新定义一种叫Chomsky的语法格式。这种格式要求每条规则只能是X -> Y1 Y2或者X -> Y的格式。实际上Chomsky语法格式保证生产的语法树总是二叉树的格式,同时任意一棵语法树总是能够转化成Chomsky语法格式。

    语法树预测算法

    假设我们已经有一个PCFG的模型,包含N、Σ、R、S、p(x)等参数,并且语法树总数Chomsky语法格式。当输入一个句子x1, x2, ... , xn时,我们要如何计算句子对应的语法树呢?
    第一种方法是暴力遍历的方法,每个单词x可能有m = len(N)种取值,句子长度是n,每种情况至少存在n个规则,所以在时间复杂度O(m*n*n)的情况下,我们可以判断出所有可能的语法树并计算出最佳的那个。
    第二种方法当然是动态规划,我们定义w[i, j, X]是第i个单词至第j个单词由标注X来表示的最大概率。直观来讲,例如xi, xi+1, ... , xj,当X=PP时,子树可能是多种解释方式,如(P NP)或者(PP PP),但是w[i, j, PP]代表的是继续往上一层递归时,我们只选择当前概率最大的组合方式。特殊情况下,w[i, i, X] = p(X -> xi)。因此,动态规划的方程可以表示为w[i, j, X] = max (p(X -> Y Z) * w(i, s, Y) * w(s+1, j, Z))。关于动态规划方法,leetcode里有不少案例可以说明。

    语法解析按照上述的算法过程便完成了。虽说PCFG也有一些缺点,例如:1)缺乏词法信息;2)连续短语(如名词、介词)的处理等。但总体来讲它给语法解析提供了一种非常有效的实现方法。


    展开全文
  • 编译原理之文法

    万次阅读 2018-09-18 21:31:16
    文法:以有穷的集合描述无穷的计划的工具。 字母表:元素的非空有穷集合,其中的元素称为符号,因此也叫符号集。 符号串:由字母表中的元素组成的任何有穷序列,串中的元素个数叫做符号串的长度,空符号串ε,长度...

    文法:以有穷的集合描述无穷的计划的工具。

    字母表:元素的非空有穷集合,其中的元素称为符号,因此也叫符号集。

    符号串:由字母表中的元素组成的任何有穷序列,串中的元素个数叫做符号串的长度,空符号串ε,长度为0。
    符号串的运算:
    连接-符号串x = ab,y=cd, xy = abcd
    方幂-z=xn,当n = 0, z = ε,当 n = 2, z = xx
    集合的闭包-∑* = ∑0 ∪∑1 ∪∑2 ∪…∪∑n
    ∑+ 为正闭包 = ∑1 ∪∑2 ∪…∪∑n

    规则|产生式|生成式,是形如α->β的有序对,读作α定义为β,相同左部的产生式可缩写A->a|b|c|d。

    文法定义的形式-四元组(Vn,Vt,P,S): Vn为非终结符集,Vt 为终结符集,P为规则集,S为识别符|开始符,至少要在一个规则中作为左部出现,Vn ∩ Vt = ∅。

    直接推导=>, 长度为n(n>=1)的推导+=>,长度为n(n>=0)的推导=>【+在=上面】,v=0S1,w=0011,直接推导:0S1 =>0011,使用规则:S->01,γ=0,δ=1;可以说w是v的直接推导,或者w直接归约于v,由识别符号S推导出来的符号串称为文法的句型,如果该符号串仅由终结符号组成,称为句子。

    G[S]称为文法,L[G]为文法的集合表示形式
    若L[G1] = L[G2],则称文法G1和G2是等价的。
    G[S]:S->0S1,S->01
    G[A]:A->0R,A->01,R->A1
    L[S]=L[A]={0n1n|n>=1}

    根据对文法施加不同的限制,分成4种类型。
    0型或短语文法:文法的每个产生式α->β都是α、β属于字符集的闭包区间内且α至少包含有一个非终结符;左边有非终结符,右边有终结符;0型文法的能力相当于图灵机(Turing)。或者说,任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言。总之一般文法都是0型文法。

    1型文法:又称为上下文有关文法,

    • α->β均满足|α|<=|β|, 除了S->ε外;小的推出大的或者相等的; 
    • 式子左边可以有多个字符,但必须有一个终结符
    • 式子右边可以有多个字符,可以是终结符,也可以是非终结符,但必须是有限个字符

    2型文法:又称为上下文无关文法,

    • 式子左边只能有一个字符,而且必须是非终结符
    • 式子右边可以有多个字符,可以是终结符,也可以是非终结符,但必须是有限个字符

    3型文法:又称为正规文法(正规文法又包括左线性文法和右线性文法)

    • 式子左边只能有一个字符,而且必须是非终结符
    • 式子右边最多有二个字符。如果有二个字符必须是一个终结符和一个非终结符,如果只有一个字符,那么必须是终结符。
    • 式子右边的格式一定要一致。也就是说如果有一个是(终结符+非终结符)那么所有的式子都必须是(终结符+非终结符), 如果有一个是(非终结符+终结符),那么所有的式子都必须是(非终结符+终结符)

    正规文法——左线性文法:
    (1):必须是三型文法
    (2):式子右边的产生是(非终结符+终结符)的格式
    正规文法——右线型文法:
    (1):必须是三型文法

    (2):式子右边的产生式是(终结符+非终结符)的格式

    描述一种上下文无关的推导工具:句型的推导和语法树(推导树)

    给定文法G(VN,VT,P ,S),对于G的任何句型都能构造与之关联的语法树。这棵树满足下面四个条件:
    ① 每个结点都有一个标记,此标记是V的 一个符号。(说的是节点一定是终结符或非终结符)
    ② 根的标记是S。(说的是树根的标记是开始符号S)
    ③ 若一结点标记A,至少有一个从它出发的分枝,则A肯定在Vn中(说的是如果一个节点有分支的话,这个节点一定是非终结符)
    ④ 如果标记为A,有n个从它出发的分枝,并且这些分枝的结点的标记(从左到右)为B1, B2,…,Bn,那么A→B1B2,…,Bn一定是P中的一个产生式。(说的是从A出发的叶子节点从左到右排列,一定是P中规则的一个产生式)
    1

    推导的每一步都是对最左非终结符进行替换,称为最左推导;最右推导也称规范推导

    句型的分析:自上而下的分析和自下而上的分析。

    一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语;相对于非终结符的短语
    如果子树中不再包含其他的子树,即A只能推导出b,而b不能再推出其他的式子,则b为此句型的直接短语;相对于规则的直接短语
    直接短语中的最左直接短语为该句型的句柄[最右推导,右句型];某句型的句柄
    案例:
    S -> a|b|(T)
    T -> TdS|S
    证明(Sd(T)db)是S的一个句型,并求出短语,直接短语,句柄
    此文法的抽象语法树为:
    1
    由此可得S=(Sd(T)db)为此文法的一个句型:
    • 短语:S,(T),b,Sd(T),Sd(T)db,(Sd(T)db)
    • 直接短语:S,(T),b
    • 句柄:S

    文法的实用限制:
    有害规则:形如U->U的规则,没用,容易引起二义性;
    多余规则:非终结符不在任意规则的右部出现,不可到达;非终结符不能推导出终结符,不可终止;

     

    展开全文
  • 谷歌搜索语法(一)基本语法

    万次阅读 多人点赞 2019-11-16 12:21:50
    Google是一款十分强大的搜索引擎,黑客们常常借助它搜索网站的一些敏感目录和文件,甚至可以利用它的搜索功能来自动攻击那些有漏洞的网站;而有些人可以通过搜索把某个个人的信息,包括住址、电话号码、出生年月等都...
  • 语法

    2019-12-05 21:46:44
  • 1. -(으)ㄹ 턱이 없다 用于动词词干后,表示没有理由做某事,即不会去做某事。 예: 기대도 하지만! 그 사람이 올 턱이 없어 2. -(으)리라고 用于动词词干后,其后与결심하다,말하다等动词结合使用 ...
  • 1.2Java基础语法详解

    2020-07-29 10:02:50
    文章目录Java基础语法语法格式编写Java程序代码时,需要特别注意几个关键点:关键字关键字的定义和特点:标识符定义:组成:命名规范变量变量的概念:变量的基本语法格式如下:变量的定义示例:变量的分类数据类型...
  • 韩语语法(三)

    2011-08-20 08:46:53
    ~다면서요? 用于说话人确认他所听到的事情是否属实。 동사(动词的几种用法): .../******************************************************/ ...A:선생님,한국 사람들은 매운 음식을 잘 먹는다면서요?...
  • Markdown语法小结

    万次阅读 2018-01-03 20:01:50
    Markdown语法小结语法基础1.标题# 一级标题 ## 二级标题 ### 三级标题 #### 四级标题 ##### 五级标题 ###### 六级标题 2.字体*斜体* **粗体** ~~删除线~~ 3.列表无序列表(使用*,+,-表示) - 一级 + 二级 * 三级 ...
  • wireshark过滤语法总结

    万次阅读 多人点赞 2011-12-09 22:47:06
    抓包采用wireshark,提取特征时,要对session进行过滤,找到关键的stream,这里总结了wireshark过滤的基本语法,供自己以后参考。(脑子记不住东西) wireshark进行过滤时,按照过滤的语法可分为协议过滤和内容...
  • 很多想开发iOS,或者正在开发iOS的程序员以前都做过Java或者C++,当第一次看到Objective-C的代码时都会头疼,Objective-C的代码在语法上和Java, C++有着很大的区别,有的同学会感觉像是看天书一样。不过,语言都是...
  • Markdown常用语法(缩进、换行、字体大小等)

    万次阅读 多人点赞 2018-10-16 21:51:29
    Markdown常用语法常用语法1. 实现缩进2. 实现换行3. 字体大小、颜色、类型、加粗、倾斜4. 代码块5. 超链接6. 分割线7. 标题 常用语法 old brother, stable &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&...
  • Python语法糖系列

    万次阅读 2019-01-23 22:42:16
    语法糖说明 语法糖(Syntactic sugar): 计算机语言中特殊的某种语法 这种语法对语言的功能并没有影响 对于程序员有更好的易用性 能够增加程序的可读性 简而言之,语法糖就是程序语言中提供[奇技淫巧]的一...
  • shell脚本基本语法详解

    万次阅读 多人点赞 2019-11-16 17:22:43
    /bin/bash,因为linux里面不仅仅只有bash一个解析器,还有其它的,它们之间的语法会有一些不同,所以最好加上这一句话,告诉系统要用这个解析器。一.shell变量shell变量和一些编程语言不同,一般shell的变量赋值的...
  • 【Emmet】HTML速写之Emmet语法规则

    万次阅读 多人点赞 2020-09-09 17:26:30
    ...一堆的标签、属性、括号等,头疼。这里推荐一个Emmet语法规则,让你写的时候爽到飞起,能大大提高代码...Emmet是一款插件,只要能安装他的编辑器都能使用,大部分编辑器都可以使用该语法规则,我们平时开发的Sublim...
  • 编译原理:语法分析器

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

    千次阅读 2019-01-02 15:40:10
    语法糖(Syntactic sugar),也译为糖衣语法,是由英国计算机科学家彼得·约翰·兰达(Peter J. Landin)发明的一个术语,指计算机语言中添加的某种语法,这种语法对语言的功能并没有影响,但是更方便程序员使用。...
  • Redy语法分析--抽象语法树简介

    万次阅读 2014-07-27 12:52:24
    抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌套...
1 2 3 4 5 ... 20
收藏数 2,148,083
精华内容 859,233
关键字:

语法