LR分析法的详细阐述

发布时间:2023-05-17

一、LR分析法属于

LR分析法属于自底向上分析法。在语法上LR范式更加自由,适合表示丰富的语言结构。

二、LR分析法在自左至右扫描输入

用于在不确定的环境中为输入符号串建立一个带有分析树的结构模型。LR分析法通过自左至右扫描输入,同时探测输入串中已有的最长前缀符合哪个产生式,以达到操作序列构造的目的。

三、LR分析法是谁

LR分析法的出现可以追溯到20世纪70年代,Thomas J. K.Clark和Stephen C. Johnson等人先后提出了LR分析法的具体实现,并在编译程序的设计中使用了该方法。

四、LR分析法分析能力最强

LR分析法具有分析能力最强的优点。其分析的范围包括了所有LR(k)文法能够接受的上下文无关文法,并且超越了上下文相关文法的范畴,可以分析更多的文法。

五、LR分析法适合表达式

LR分析法在表达式文法分析中有着广泛应用。略去书写时需要的括号等繁琐内容,减少了编译程序在分析表达式时的复杂度。

六、LR分析法实验报告

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * LR(0)文法分析器
 */
public class LRAnalyzer {
    private List<String> inputSymbol; // 输入符号串
    private List<String> stack; // 栈
    private List<String> actionList; // 动作表
    private List<String> gotoList; // 状态转移表
    private List<String> grammar; // 产生式
    private int index; // 输入符号串索引
    private String currentSymbol; // 当前符号
    private Stack<String> stateStack; // 状态栈 
    public LRAnalyzer(List<String> inputSymbol) {
        this.inputSymbol = inputSymbol;
        stack = new ArrayList<>();
        actionList = new ArrayList<>();
        gotoList = new ArrayList<>();
        grammar = new ArrayList<>();
        index = 0;
        stateStack = new Stack<>();
    }
    // 初始化
    public void init(List<String> stack, List<String> actionList, List<String> gotoList, List<String> grammar) {
        this.stack = stack;
        this.actionList = actionList;
        this.gotoList = gotoList;
        this.grammar = grammar;
    }
    // 分析
    public void analyze() {
        // 将状态0入栈
        stateStack.push("0");
        // 读入第一个符号
        currentSymbol = inputSymbol.get(index++);
        // 不断执行移入或归约操作
        while (true) {
            // 获取当前状态,也就是状态栈栈顶元素
            String state = stateStack.peek();
            // 在动作表中查找对应状态和符号的动作类型
            String actionType = actionList.get(Integer.parseInt(state) * stack.size() + stackIndex(currentSymbol));
            // 如果是移入操作
            if (actionType.startsWith("s")) {
                // 将状态入栈
                stateStack.push(actionType.substring(1));
                // 将符号入栈
                stack.add(currentSymbol);
                // 读入下一个符号
                currentSymbol = inputSymbol.get(index++);
            }
            // 如果是归约操作
            else if (actionType.startsWith("r")) {
                // 获取产生式序号
                int grammarIndex = Integer.parseInt(actionType.substring(1));
                // 获取产生式右部符号串
                String grammarRight = grammar.get(grammarIndex).substring(grammar.get(grammarIndex).indexOf('>') + 1);
                // 弹出状态和符号,执行归约操作
                for (int i = 0; i < grammarRight.length(); i++) {
                    stateStack.pop();
                    stack.remove(stack.size() - 1);
                }
                // 根据转移表和归约符号将状态入栈
                String newState = gotoList.get(Integer.parseInt(stateStack.peek()) * stack.size() + stackIndex(grammar.get(grammarIndex).substring(0, 1)));
                stateStack.push(newState);
                stack.add(grammar.get(grammarIndex).substring(0, 1));
            }
            // 如果是接受操作
            else if (actionType.equals("acc")) {
                System.out.println("分析成功!");
                return;
            }
            // 如果是错误操作
            else {
                System.out.println("分析失败!");
                return;
            }
        }
    }
    // 获取符号在栈中的索引
    private int stackIndex(String symbol) {
        for (int i = 0; i < stack.size(); i++) {
            if (stack.get(i).equals(symbol)) {
                return i;
            }
        }
        return -1;
    }
}

七、LR分析法是一种

LR分析法是一种自底向上语法分析方法,可以分析上下文无关文法和一些上下文相关文法,具有分析能力最强的优点。

八、LR分析法是自上而下吗

LR分析法不是自上而下的分析方法。由于LR分析法的本质是确定有限状态自动机,因此它依赖于上下文的存储,是自底向上的分析方法。

九、LR分析法的可归约串是

可归约串是指在输入符号串末尾添加一个特定符号“#”,使得分析表中有接受状态。LR分析法的可归约串为输入符号串加上终结符“#”,即可进行成功的语法分析。