精华内容
下载资源
问答
  • 编译原理 自底向上语法分析
    2020-05-12 16:07:00

    引言

    自底向上的语法分析相当于从叶子节点开始向上一直到根部构造一棵语法树。我们将使用移入-归约法完成这一过程。

    归约

    • 定义:一个与某产生式体相匹配的特定子串被替换成该产生式头部的非终结符号。相当于反向的最右推导。

    举例:

    给定文法:S->aABe
    A->Abc | b
    B->d

    串abbcde可以由推导S=>rmaABe=>rmaAde=>rmaAbcde=>rmabbcde得到。
    那么逆置最后一步,把b替换成非终结符A就是归约,并且称这个b为句柄。

    • 句柄:如果有S->αAb->αβb,那么紧跟α的产生式A->β是αβb的一个句柄。非正式地讲,β就是句柄。这里要满足的重要条件就是从句柄继续逆推一定能得到开始符号。如果不能构成一个以开始符号为起点的推导,那么这样的产生式不能构成句柄。

    仍按上例:abbcde的句柄为b,aAbcde的句柄为Abc,等等。

    句柄右侧的串只含终结符号,因为如果含有非终结符号,那必然不是最右推导。在有二义性的文法中不是唯一的,这很好理解,因为产生式不是唯一的。

    移入-归约分析法

    四种动作:
    • 移进 (shift):把下一个输入符号移进栈 (栈顶)
    • 归约 (reduce):分析器知道句柄的右端已在栈顶,然后确定句柄的左端在栈中的位置,再决定用什么样的非终结符代替句柄
    • 接受 (accept):分析器宣告分析成功
    • 报错 (error):分析器发现语法错误,调用错误恢复例程

    只要恰当地进行以上四种操作,就能完成语法树的构建。我们先看一个手工构建的例子。
    已知以下文法:E->E + T | T
    T->T * F | F
    F->(E) | id
    用移入-归约语法分析器构建语法树。
    在这里插入图片描述
    栈内加入结束符,然后逐个字符移入,在正确的时候归约,最后得到开始符。这里的问题是:
    1、何时移入,何时归约?
    2、选择哪个子串进行归约?
    3、进行归约时,选择哪个产生式进行归约?
    看起来,我们又需要一个像非递归的自顶向下分析法的预测分析表的东西。

    更多相关内容
  • 1、 理解自底向上语法分析方法; 2、 用LR分析技术实现语法分析器; 3、 熟练掌握LR分析程序的构造方法。
  • 自底向上语法分析

    2019-07-16 11:22:00
    什么是自底向上语法分析 一个自底向上语法分析过程对应为一个输入串构造语法分析书的过程,它从叶子节点开始,通过shift和reduce操作逐渐向上到达根节点 自底向上语法分析需要一个堆栈来存放解析的符号,...

    什么是自底向上的语法分析

    一个自底向上的语法分析过程对应为一个输入串构造语法分析书的过程,它从叶子节点开始,通过shift和reduce操作逐渐向上到达根节点

    自底向上的语法分析需要一个堆栈来存放解析的符号,例如对于如下语法:

    0.  statement -> expr
    1.  expr -> expr + factor
    2.           | factor
    3.  factor ->  ( expr )
    4.           | NUM

    来解析1+2

    stackinput
    null1 + 2
    NUM+ 2开始读入一个字符,并把对应的token放入解析堆栈,称为shift操作
    factor+ 2根据语法推导式,factor -> NUM,将NUM出栈,factor入栈,这个操作称为reduce
    expr+ 2这里继续做reduce操作,但是由于语法推导式有两个产生式,所以需要向前看一个符合才能判断是进行shift还是reduce,也就是语法解析的LA
    expr +2shift操作
    expr + NUMnullshift操作
    expr + factornull根据fator的产生式进行reduce
    exprnullreduce操作
    statementnullreduce操作

    此时规约到开始符号,并且输入串也为空,代表语法解析成功

    所以实现自底向上的语法解析关键就是识别堆栈上是应该进行shift还是reduce操作。

    • 进行暴力匹配,搜索堆栈上的符号和所有的语法推导式进行匹配 x
    • 构造一个状态机来根据堆栈压入或弹出后的状态来决定是否进行reduce操作

    使用状态表来指导操作

    • 先构建有限状态自动机

      ed893c38ly1g50w88akukj20uq0aydhg.jpg

    • 再根据状态机构建跳转表

    EOINUM+exprterm
    0errs1errstate_2state_3
    1r3errr3errerr
    2Accepterrs4errerr
    3r2errr2errerr
    4errs1errerrstate_5
    5r1errr1errerr

    有限状态自动机的构建

    0.  s -> e
    1.  e -> e + t
    2.  e -> t
    3.  t -> t * f
    4.  t -> f
    5.  f -> ( e )
    6.  f -> NUM

    对起始推导式做闭包操作

    先在起始产生式->右边加上一个.

    s -> .e

    对.右边的符号做闭包操作,也就是说如果 . 右边的符号是一个非终结符,那么肯定有某个表达式,->左边是该非终结符,把这些表达式添加进来

    s -> . e
    e -> . e + t
    e -> .t

    对新添加进来的推导式反复重复这个操作,直到所有推导式->右边是非终结符的那个所在推导式都引入

    private void makeClosure() {
            
            Stack<Production> productionStack = new Stack<Production>();
            for (Production production : productions) {
            productionStack.push(production);
          }
                    
          while (productionStack.empty() == false) {
                Production production = productionStack.pop();
                int symbol = production.getDotSymbol();
                ArrayList<Production> closures = productionManager.getProduction(symbol);
                for (int i = 0; closures != null && i < closures.size(); i++) {
                    if (closureSet.contains(closures.get(i)) == false) {
                        closureSet.add(closures.get(i));
                        productionStack.push(closures.get(i));
                    }
                }
            }
        }

    对引入的产生式进行分区

    把 . 右边拥有相同非终结符的表达式划入一个分区,比如

    e -> t .
    t ->t . * f

    就作为同一个分区。最后把每个分区中的表达式中的 . 右移动一位,形成新的状态节点

    private void partition() {
            for (int i = 0; i < closureSet.size(); i++) {
                int symbol = closureSet.get(i).getDotSymbol();
                if (symbol == SymbolDefine.UNKNOWN_SYMBOL) {
                    continue;
                }
                
                ArrayList<Production> productionList = partition.get(symbol);
                if (productionList == null) {
                    productionList = new ArrayList<Production>();
                    partition.put(closureSet.get(i).getDotSymbol(), productionList);
                }
                
                if (productionList.contains(closureSet.get(i)) == false) {
                    productionList.add(closureSet.get(i));  
                }
            } 
        }

    对所有分区节点构建跳转关系

    根据每个节点 . 左边的符号来判断输入什么字符来跳入该节点

    比如, . 左边的符号是 t, 所以当状态机处于状态0时,输入时 t 时, 跳转到状态1。

    private void makeTransition() {
        for (Map.Entry<Integer, ArrayList<Production>> entry : partition.entrySet()) {
          GrammarState nextState = makeNextGrammarState(entry.getKey());
          transition.put(entry.getKey(), nextState);
        }
    }

    对所有新生成的节点重复构建

    最后对每个新生成的节点进行重复的构建,直到完成所有所有的状态节点的构建和跳转

    private void extendFollowingTransition() {
        for (Map.Entry<Integer, GrammarState> entry : transition.entrySet()) {
          GrammarState state = entry.getValue();
          if (state.isTransitionMade() == false) {
            state.createTransition();
          }
        }
    }

    LookAhead集合对有限状态机的完善

    让我们来看节点1的两个产生式

    e -> t .
    t -> t . * f

    这时候通过状态节点0输入t跳转到节点1,但是这时候状态机无法分清是做shift还是reduce操作, 这种情况也就是称之为shift / reduce矛盾。

    SLR(1)语法

    在之前的LL(1)语法分析过程中,有一个FOLLOW set,也就是指的是,对某个非终结符,根据语法推导表达式构建出的所有可以跟在该非终结符后面的终结符集合,我们称作该非终结符的FOLLOW set.

    FOLLOW(s) = {EOI}
    FOLLOW(e) = {EOI, },+}
    FOLLOW(t) = {EOI, }, + , * } 
    FOLLOW(f) = {EOI, }, +, * }

    只要判断当前的输入字符是否在该产生式的follor set就可以判断是不是应该进行reduce操作,但是这只能解决一部分的shift / reduce矛盾

    所以就需要LALR(1)语法分析了,通过向前看一个符号来解决shift/reduce矛盾

    LALR(1)

    对于shift.reduce矛盾,我们需要考虑的事,当我们做了reduce操作后,在状态机当前上下文环境下,是否能合法的跟在reduce后的非终结符的后面。

    这个集合,我们称之为look ahead set, 它是FOLLOW set 的子集。

    look ahead set的构建

    s -> α .x β, C
    x -> . r

    C是S的look ahead集合,α, β, r 是0个或多个终结符或非终结符的组合,x是非终结符,那么 x -> . r 的look ahead就是FIRST(β C)

    添加look ahead set只要修改在构建闭包部分

    private void makeClosure() {
            Stack<Production> productionStack = new Stack<Production>();
          for (Production production : productions) {
            productionStack.push(production);
          }
                    
            while (!productionStack.empty()) {
                Production production = productionStack.pop();
                if (SymbolDefine.isSymbolTerminals(production.getDotSymbol()) == true) {
                        continue;   
                    }
                
                int symbol = production.getDotSymbol();
                ArrayList<Production> closures = productionManager.getProduction(symbol);
                ArrayList<Integer> lookAhead = production.computeFirstSetOfBetaAndC();
                
                Iterator it = closures.iterator();
                while (it.hasNext()) {
                    Production oldProduct = (Production) it.next();
                    Production newProduct = (oldProduct).cloneSelf();
                    newProduct.addLookAheadSet(lookAhead);
                    
                    if (!closureSet.contains(newProduct)) {
                        closureSet.add(newProduct);
                        productionStack.push(newProduct);
                        
                        removeRedundantProduction(newProduct);
                    }
                }
            }
        }

    有限状态自动机的压缩

    在状态机里有很多状态节点,产生式以及产生式中,点的位置是一样的,唯一不同的是,两个节点中,产生式对应的look ahead集合不一样,这样的节点,我们就可以将他们结合起来。

    State Number: 1
    EXPR -> TERM .look ahead set: { EOI }
    TERM -> TERM .TIMES FACTOR look ahead set: { EOI }
    TERM -> TERM .TIMES FACTOR look ahead set: { TIMES }
    EXPR -> TERM .look ahead set: { PLUS }
    TERM -> TERM .TIMES FACTOR look ahead set: { PLUS }
    
    State Number: 8
    EXPR -> TERM .look ahead set: { RIGHT_PARENT }
    TERM -> TERM .TIMES FACTOR look ahead set: { RIGHT_PARENT }
    TERM -> TERM .TIMES FACTOR look ahead set: { TIMES }
    EXPR -> TERM .look ahead set: { PLUS }
    TERM -> TERM .TIMES FACTOR look ahead set: { PLUS }

    像这种产生式一样,只有look ahead集合不同的就可以合并为一个节点

    public void addTransition(GrammarState from, GrammarState to, int on) {
            if (isTransitionTableCompressed) { 
                from = getAndMergeSimilarStates(from);
                to   = getAndMergeSimilarStates(to);    
            } 
            HashMap<Integer, GrammarState> map = transitionMap.get(from);
            if (map == null) {
                map = new HashMap<Integer, GrammarState>();
            } 
    
            map.put(on, to);
            transitionMap.put(from, map);
        }

    通过状态机构建跳转表

    通过之前的算法已经可以给出各个节点之前的跳转关系,但是还有一个信息没有表现出来,就是对于当前的输入是否应该进行reduce

    创建redcueMap

    先看点是否在产生式的最后来判断是否可以做reduce操作,

    private void  reduce(HashMap<Integer, Integer> map, ArrayList<Production> productions) {
      for (int i = 0; i < productions.size(); i++) {
        if (productions.get(i).canBeReduce()) {
          ArrayList<Integer> lookAhead = productions.get(i).getLookAheadSet();
          for (int j = 0; j < lookAhead.size(); j++) {
            map.put(lookAhead.get(j), (productions.get(i).getProductionNum()));
          }
        }
      }
    }

    创建跳转表

    public HashMap<Integer, HashMap<Integer, Integer>> getLRStateTable() {
            Iterator it = null;
            if (isTransitionTableCompressed) {
                it = compressedStateList.iterator();
            } else {
                it = stateList.iterator();
            }
            
            while (it.hasNext()) {
                GrammarState state = (GrammarState) it.next();
                HashMap<Integer, GrammarState> map = transitionMap.get(state);
                HashMap<Integer, Integer> jump = new HashMap<Integer, Integer>();
            
                if (map != null) {
                    for (Entry<Integer, GrammarState> item : map.entrySet()) {
                        jump.put(item.getKey(), item.getValue().stateNum);
                    }
                }
                
                HashMap<Integer, Integer> reduceMap = state.makeReduce();
                if (reduceMap.size() > 0) {
                    for (Entry<Integer, Integer> item : reduceMap.entrySet()) {
                        
                        jump.put(item.getKey(), -(item.getValue()));
                    }
                }
                
                lrStateTable.put(state.stateNum, jump);
            }
            
            return lrStateTable;
        }

    转载于:https://www.cnblogs.com/secoding/p/11193716.html

    展开全文
  • 1) 任意输入一个文法G; 2) 判断该文法是否为算符文法;... 对应的语法树;能够输出分析过程中每一步符号 栈的变化情况以及根据当前最左素短语进行归约 的过程。如果该句子非法则进行相应的报错处理。
  • 编译原理实验-PL0自底向上语法分析

    千次阅读 2019-11-29 19:04:57
    最近顶着考研的压力去做了一下编译原理的实验,实验的要求是写一个PL/0语法的编译器,一开始想从网上找找有没有现成的代码改一改就完事了,结果百度的结果都是递归下降分析,而老师的课程大部分都在讲自底向上分析的...

    最近顶着考研的压力去做了一下编译原理的实验,实验的要求是写一个PL/0语法的编译器,一开始想从网上找找有没有现成的代码改一改就完事了,结果百度的结果都是递归下降分析,而老师的课程大部分都在讲自底向上分析的知识,而我甚至不知道这个文法是不是SLR的,所以为了讲实验一咬牙干脆自己写一个好了,如果算出来是SLR的就去讲实验,不是SLR大不了分不要了,因为LL(1)表的构造实在是让人难受,幸好结果证明这文法确实是SLR的。
    有限的时间中大多数都花在了构造语法分析表的部分,所以后面的翻译执行并没有完成。

    完整的python实现程序已经上传到了码云,需要的话可以参考:
    编译原理实验-PL0自底向上分析

    1.原文法

    〈程序〉→〈分程序>.

    〈分程序〉→ [<常量说明部分>][<变量说明部分>][<过程说明部分>]〈语句〉

    <常量说明部分> → CONST<常量定义>{ ,<常量定义>};

    <常量定义> → <标识符>=<无符号整数>

    <无符号整数> → <数字>{<数字>}

    <变量说明部分> → VAR<标识符>{ ,<标识符>};

    <标识符> → <字母>{<字母>|<数字>}

    <过和说明部分> → <过程首部><分程度>;{<过程说明部分>}

    <过程首部> → procedure<标识符>;

    <语句> → <赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句>|<读语句>|<写语句>|<复合语句>|<空>

    <赋值语句> → <标识符>:=<表达式>

    <复合语句> → begin<语句>{ ;<语句>}end

    <条件> → <表达式><关系运算符><表达式>|ood<表达式>

    <表达式> → [+|-]<项>{<加减运算符><项>}

    <项> → <因子>{<乘除运算符><因子>}

    <因子> → <标识符>|<无符号整数>|(<表达式>)

    <加减运符> → +|-

    <乘除运算符> → *|/

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

    <条件语句> → if<条件>then<语句>

    <过程调用语句> → call<标识符>

    <当型循环语句> → while<条件>do<语句>

    <读语句> → read(<标识符>{ ,<标识符>})

    <写语句> → write(<标识符>{,<标识符>})

    <字母> → a|b|c…x|y|z

    <数字> → 0|1|2…7|8|9

    2.词法分析

    这里我用字符串分析的方法来做的,具体逻辑可以见代码语法分析树文件夹下的tokens.py。在词法分析的同时,我把一部分非终结符变成了终结符方便处理:

    终结符
    const var procedure begin end ood if then while do read call write
     := = { } ( ) ; , .
    id-<标识符> 
    un-<无符号整数>  
    re-<关系运算符>  #|<|<=|>|>=
    mn-<加减运算符> +|-
    td-<乘除运算符> *|/
    

    3.状态分析表构造

    自底向上的分析方法需要状态分析表才能够实现,所以其实我最主要干的事就是造了这个分析表。
    首先需要改写文法,因为当前这种文法表示形式是不能去用所学的算法构造分析表的,所以我改成了等价文法(其实并不等价,那个#当做终结符用了,所以其实最后结果中的#并没有当不等号用,如果需要可以再完善这个文法):

    S→<程序>
    <程序>→<分程序>.
    <分程序>→ <常量说明部分><变量说明部分><过程说明部分><语句>
    <常量说明部分>→
    <常量说明部分> → const <常量定义><常量定义组>;
    <常量定义组>→,<常量定义><常量定义组>
    <常量定义组>→
    <常量定义> → id=un
    <变量说明部分>→
    <变量说明部分> → var <参数组>; 
    <参数组>→id<标识符组>
    <标识符组>→,id<标识符组>
    <标识符组>→
    <过程说明部分>→
    <过程说明部分> → <过程首部><分程序>;<过程说明部分>
    <过程首部> → procedure id;
    <语句> → <赋值语句>
    <语句> → <条件语句>
    <语句> → <当型循环语句>
    <语句> → <过程调用语句>
    <语句> → <读语句>
    <语句> → <写语句>
    <语句> → <复合语句>
    <语句> →
    <赋值语句> → id:=<表达式>
    <条件语句> → if<条件>then<语句>
    <条件> → <表达式>re<表达式>
    <条件> → ood<表达式>
    <表达式> → <项><表达式组>
    <表达式组> → <加减运符><项><表达式组> 
    <表达式组> →
    <加减运符>→mn
    <项>→<因子><因子组>
    <因子组> → td<因子><因子组>
    <因子组>→
    <因子> → id
    <因子> → un
    <因子> →(<表达式>)
    <读语句> → read(<参数组>)
    <写语句> → write(<参数组>)
    <复合语句> → begin<语句><中间语句>end
    <中间语句>→;<语句><中间语句>
    <中间语句>→
    <当型循环语句> → while<条件>do<语句>
    <过程调用语句> → call id
    

    一开始手算了一点,算着算着就发现这玩意手算估计我当天晚上就不用睡觉了:
    在这里插入图片描述于是决定开始写程序去算,具体的逻辑实在太过复杂,First,Follow还有最后的状态收集打印都花了我不少时间,这里直接讲述一下分析表生成程序的用法,所有关于分析表生成的程序都在状态表构造V2目录下:

    3.1.将文法保存在gra.txt

    在这里插入图片描述如图,将自己的文法写到gra.txt中。

    3.2.运行程序得到分析表

    在命令行键入

    python3 main.py
    

    即可运行程序
    在这里插入图片描述
    如图,程序运行会打印出所有状态,可以利用管道把这个状态输出到文件中便于进行调试。这里的xtzdj.csv就是生成的分析表,可用Excel打开查看:
    在这里插入图片描述这里行是状态,列是终结符或者非终结符,表中单元则是转移或者规约动作。

    4.进行语法分析

    得到语法分析表之后,就可以愉快的分析源程序的语法了,其实编写程序的过程并不愉快,文法的读取、状态的收集去重等还是花了我很长时间,这里也不具体讲述代码了,简单说一下程序执行方式:

    4.1.把文法和语法分析表拷贝到语法分析树v2目录下

    在这里插入图片描述如图,把这两个文件放到该目录下。

    4.2.把要分析的源码写到目录下的test.pl0中

    这里我的逻辑默认从test.pl0中读取源代码分析,如果需要的话可以修改syntax.py来修改这个默认名称。
    在这里插入图片描述

    4.3.运行语法分析程序

    在命令行中键入

    python3 syntax.py
    

    即可运行程序。
    在这里插入图片描述如图所示,成功的识别了测试的pl0程序,并打印出了语法树的树枝。即语法分析成功。

    其实到这一步整个编译器的工作并没有完成,接下来应该为其编写对应的属性文法,然后把源代码翻译成四元组,然后再是代码的优化,最后是执行,剩下的部分如果以后能闲下来再去探究吧。

    展开全文
  • 编译原理实验2-自底向上语法分析算法程序设计.doc
  • 北邮编译原理自底向上语法分析实验报告.pdf
  • 自底向上语法分析

    2021-05-10 22:55:58
    从分析树的底部(叶节点向顶部根节点方向构造分析...可以看成是将输入串归约为文法开始符号S的过程【顶向下的语法分析采用最左推导方式自底向上语法分析采用最左归约方式(反向构造最右推导)】 每次规约“句柄” ...


    参考哈工大课件

    自底向上的语法分析

    从分析树的底部(叶节点向顶部根节点方向构造分析树,可以看成是将输入串归约为文法开始符号S的过程

    自顶向下的语法分析采用最左推导方式;
    自底向上的语法分析采用最左归约方式,实际上是 反向构造最右推导

    自底向上语法分析的通用框架:移入-归约分析

    1)在对输入串的一次从左到右扫描过程中,语法分析器将零个或多个输入符号移入到栈的顶端,直到它可以对栈顶的一个文法符号串β进行归约为止
    2)它将β归约为某个产生式的左部
    3)语法分析器不断地重复这个循环,直到它检测到一个语法错误,或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时,语法分析器停止运行,并宣称成功完成了语法分析)为止
    注意:每步规约都是规范规约,每次规约“句柄”
    移入-归约分析器可采取的4种动作:

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

    移入-归约分析中存在的问题
    造成错误的原因:错误地识别了句柄

    LR分析法概述

    LR文法是最大的、可以构造出相应移入-归约语法分析器的文法类

    L: 对输入进行从左到右的扫描
    R: 反向构造出一个最右推导序列
    LR(k)分析:需要向前查看k个输入符号的LR分析。当省略(k)时,表示k =1

    1. LR 分析法的基本原理
      自底向上分析的关键问题是:如何正确地识别句柄。
      句柄是逐步形成的,用“状态”表示句柄识别的进展程度
      LR分析器基于这样一些状态来 构造自动机进行句柄的识别

    例:S→bBB
    S→·bBB 移进状态
    S→b·BB / S→bB·B 移进、待归约状态
    S→bBB· 归约状态
    注意: 产生式A→ε 只生成一个项目A→ ·

    1. LR 分析器(自动机)的总体结构
      在这里插入图片描述
      LR 分析表的结构:
    • sn:将符号a、状态n 压入栈
    • rn:用第n个产生式进行归约

    例:文法
    ① S→BB
    ② B→aB
    ③ B→b
    在这里插入图片描述

    输入bab#

    状态剩余输入动作
    0#bab#
    04#bab#0和b比较s4,移入b,添加4
    02#Bab#4和a比较r3,归约文法B→b右部长度1,在符号栈和状态栈中分别移出1个符号,在符号栈中进入B。此时栈顶是0,遇到刚规约出的B,到状态2,添加2状态
    023#Bab#2和a比较s3,移入a,添加3
    0234#Bab#3和b比较s4,移入b,添加4
    0236#BaB#4和#r3,归约文法B→b,4和b出栈,B进栈。3和B比较到状态6,6进栈
    025#BB#6和#比较r2,B→aB,36、aB出栈B进栈。2和B到到状态5,5入栈
    0#S#5和#比较r1,S→BB,25、BB出栈,S入栈。
    01#S#0和S比较到状态1,1入栈
    1遇到#成功接收acc
    • 如果ACTION[sm , ai]=acc,那么分析成功
    • 如果ACTION[sm , ai]=err ,那么出现语法错误
    //LR 分析算法
    输入:串w和LR语法分析表,该表描述了文法G的ACTION函数和GOTO函数。
    输出:如果w在 L(G)中,则输出w的自底向上语法分析过程中的归约步骤;否则给出一个错误指示。
    方法:初始时,语法分析器栈中的内容为初始状态s0,输入缓冲区中的内容为w#。
    令a为w$的第一个符号;
    while(1) { /* 永远重复*/ 
      令s是栈顶的状态;
      if ( ACTION [s,a] = st ) {
        将t压入栈中;
        令a为下一个输入符号;
      } else if (ACTION [s,a] =归约A → β ) {
        从栈中弹出│ β │个符号;
        将GOTO [t,A]压入栈中;
        输出产生式 A → β ;
      } else if (ACTION [s,a] =接受) 
          break/* 语法分析完成*/
       else调用错误恢复例程;
    }
    

    LR(0)分析

    增广文法:如果G 是一个以S为开始符号的文法,则G的增广文法 G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法
    引入增广文法的目的:使新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态
    可以把等价的项目组成一个项目集( I ) ,称为项目集闭包(Closure of Item Sets),每个项目集闭包对应着自动机的一个状态
    在这里插入图片描述

    CLOSURE()函数

    计算给定项目集I的闭包:

    CLOSURE(I) = I∪{B→ · γ | A→α·Bβ∈CLOSURE(I) , B→γ∈P}

    //CLOSURE()函数
    SetOfltems CLOSURE ( I ) {
      J = I;
      repeat
        for ( J中的每个项A → α·Bβ ) 
           for ( G的每个产生式B → γ ) 
             if ( 项B → · γ不在J中 ) 
                将B → · γ加入J中;
      until 在某一轮中没有新的项被加入到J中;
      return J;
    }
    

    LR(0) 分析过程中的冲突:移进/归约冲突& 归约归约冲突
    在这里插入图片描述
    表达式文法的LR(0)分析表含有移进/归约冲突
    在这里插入图片描述
    如果LR(0)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(0)文法

    • 不是所有CFG都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法

    SLR分析

    在这里插入图片描述

    在状态2,使用LR0文法,不向后看符号,即不考虑上下文。由followE可以知道如果下一个符号是*,则采取移进,则不会产生冲突。

    SLR分析法的基本思想
    如果集合{a1, a2, …, am}和FOLLOW(B1), FOLLOW(B2),…,FOLLOW(Bn)两两不相交,则项目集I中的冲突可以按以下原则解决:

    • 设a是下一个输入符号
      若a∈{ a1, a2, …, am },则移进a;
      若a∈FOLLOW(Bi),则用产生式Bi→γi 归约
      此外,报错

    由此就可以化解冲突,如果能够化解冲突则成为SLR文法。
    在这里插入图片描述
    在这里插入图片描述
    只对于在follow集中的符号才进行归约

    //SLR 分析表构造算法
    构造G'的规范LR(0)项集族C = { I0, I1,, In}。
    根据Ii构造得到状态i。状态i 的语法分析动作按照下面的方法决定:
      if A→α·aβ∈Ii and GOTO( Ii , a )=Ij then ACTION[ i, a ]=sj
      if A→α.Bβ∈Ii and GOTO( Ii , B )=Ij then GOTO[ i, B ]=j
      if A→α·∈Ii且A ≠ S' then for a∈FOLLOW(A) do
    ACTION[ i, a ]=rj (j是产生式A→α的编号)
      if S'→S·∈Ii then ACTION [ i , $ ]=acc;
    没有定义的所有条目都设置为“error”。
    

    SLR分析存在的问题:
    SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)
    只是归约α的一个必要条件,而非充分条件

    LR(1)分析

    对于产生式 A→α的归约,在不同的使用位置,A会要求不同的后继符号。在特定位置,A的后继符集合是FOLLOW(A)的子集。
    规范LR(1)项目:
    将一般形式为 [A→α·β, a]的项称为 LR(1) 项,其中A→αβ 是一个产生式,a 是一个终结符(这里将$视为一个特殊的终结符)
    它表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符(lookahead)

    • LR(1) 中的1指的是项的第二个分量的长度
    • 在形如[A→α·β, a]且β ≠ ε的项中,展望符a没有任何作用
    • 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约。这样的a的集合总是FOLLOW(A)的子集,而且它通常是一个真子集。
      在这里插入图片描述
      在这里插入图片描述
    展开全文
  • LR(0)自底向上语法分析 详细介绍自底向上语法分析的处理过程以及相应的问题解决方法
  • 编译原理自底向上语法分析(1)
  • 自底向上语法分析LR(1)

    千次阅读 2019-10-17 13:42:45
    自底向上分析方法,也称移进-归约分析法,粗略地说它的实现思想是对输入符号串左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,就用该产生式的左部非...
  • 基于NFA(不确定有穷自动机)与自底向上语法分析构造的正则表达式解析器
  • 自底向上语法分析的本质与原理

    千次阅读 2017-08-21 23:26:40
    语法分析的本质就是是否可以生成一颗语法树,它的叶子节点及终结符与我们程序的符号流一致,存在的正确,不存在的错误。  我们可以这样思考,我们将程序的符号表看做是语法树的叶子节点,按照文法进行反向推到,...
  • 自底向上分析语法分析程序设计与实现 一、实验任务及内容 编制一个文法的输入,从键盘、文件或文本框输入给定文法,依次存入输入缓冲区(字符型数据)。 编制一个算法,模拟LR(0)分析器的主控流程,实现对给定...
  • 自底向上语法分析的通用框架:移入-归约分析(Shift-Reduce Parsing) 【例】移入-归约分析 $表示栈底和栈顶 开始时栈中没有任何符号 第一步,将id入栈 第二步,因为id是第四个产生式的右部,所以将id归约为E,id...
  • 声明:本系列文章,是根据中国大学MOOC网 哈工大的编译原理 这门课学习而成的学习笔记。 一、底向上分析概述 底向上的语法分析 从分析树的底部(叶节点)...自底向上语法分析的通用框架 移入-归约分析(Shift-Re...
  • 编译器之语法分析自底向上基本概念算符优先SLR规范LRLALR 自底向上 基本概念 自底向上形成语法树的过程就是及逆行归约,将一堆单词串放在一起,形成某个产生式的样子,然后规约成某个产生式,所以关键就是什么时候...
  • 简单优先分析法1.基本概念通过语法树来理解这三个概念更加简单:文法G1[S]:S→ABA→bBA→AaB→aB→Sb语法树短语:若S=*=>αAδ且A=+=>β,则称β是相对于非终结符A的句型αβδ的短语。即:语法树中以非终结...
  • 编译原理-语法分析自底向上

    千次阅读 2019-11-20 20:35:22
    自底向上分析概述 LR(0) 项目自动机 LR(0) 项 增广 构造自动机--项集,项集闭包,项集投影 内核项 与 非内核项 构造自动机--GOTO函数 移入规约冲突 SLR LR(1) LALR(1) LALR分析器与LR分析器 子问题 构造自动机--完整...
  • (一)自底向上的语法分析概述自底向上语法分析自底向上语法分析从待输入的符号串开始,利用文法的产生式步步向上归约,试图归约到文法的开始符号。从语法树的角度看自底向上分析的过程是以输入符号串作为端末结点符号...
  • 编译原理作业之一,作为学习记录,若有错误或者需要改进的地方欢迎底下评论。Mind master原文件 百度网盘提取码:i6cr
  • 编译原理顶向下语法分析源代码+实验报告
  • 先用代码占个坑,等期末结束了再补详细解释。。。 /* 2020-06-20 by 软件工程172 202171139 TDM-GCC 4.9.2 64-bit -std=C++11 */ #include #... cout 算符优先分析表\n4.检测输入串\n5.退出\n"; while(true) { cout...
  • 编译原理及实现技术:12.语法分析_自底向上语法分析概述、简单优先方法.ppt
  • 实验三 自底向上语法分析

    千次阅读 2018-06-18 08:41:48
    // 首先,感谢孙同学的Java版代码,让我有了参考 // 下面上C++代码,文件操作部分自行改写即可 #include &amp;lt;iostream&amp;gt; #include &amp;lt;fstream&amp;gt; ...amp

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,978
精华内容 4,791
关键字:

自底向上语法分析