什么是编译器设计中没有回溯的自顶向下解析?
有两种没有回溯的自顶向下解析,如下所示-
递归下降解析器
预测解析器
递归下降解析器
实现一组递归过程来处理输入而不回溯的自顶向下解析器被称为递归下降解析器,解析被称为递归下降解析。如果以有效执行过程调用的语言编写,递归过程可以被编写并且足够有效。
文法中的每个非终结符都有一个过程。可以考虑一个全局变量lookahead,影响当前输入的token和一个过程匹配(ExpectedToken)是在解析过程中识别下一个token并推进输入流指针的动作,使得lookahead指向下一个要处理的token解析。Match()实际上是调用词法分析器以获取下一个标记。
预测解析器
预测解析器也称为非递归预测解析。预测解析器是通过显式处理活动记录堆栈来实现递归下降解析的有效方法。预测解析器具有输入、堆栈、解析表和输出。输入包括要解析的字符串,后跟$,即右端标记。
堆栈包括一系列语法符号,前面是$,堆栈底部标记。最初,堆栈包含以$开头的语法的起始符号。解析表是一个二维数组M[A,a],其中'A'是一个非终结符,'a'是一个终结符或符号$。
解析器由执行如下的程序控制-程序决定X堆栈顶部的符号和'a'当前输入符号。这两个符号决定解析器的动作。
有以下三种可能
如果X=a=$,解析器终止并声明解析的成功整合。
如果X=a≠$,解析器将X从堆栈中弹出并将输入指针前进到下一个输入符号。
如果X是非终结符,程序会查询解析表M的条目M[X,a]。该条目将是语法的X产生式或错误条目。如果M[X,a]=[X→UVW],解析器将堆栈顶部的X替换为UVW(U在顶部)。作为输出,语法执行与此产生式相关联的语义动作,目前,它可以假设只是打印使用的产生式。如果M[X,a]=错误,解析器调用错误恢复例程。