编译器设计 - 解析类型

• 

  简述

  语法分析器遵循由上下文无关语法定义的生产规则。产生式规则的实现方式（推导）将解析分为两种：自顶向下解析和自底向上解析。

  

  自顶向下解析

  当解析器从起始符号开始构建解析树，然后尝试将起始符号转换为输入时，称为自顶向下解析。

  • Recursive descent parsing: 是自顶向下解析的一种常见形式。它被称为递归，因为它使用递归过程来处理输入。递归下降解析受到回溯的影响。
  • Backtracking：这意味着，如果一个产生式的派生失败，语法分析器使用相同产生式的不同规则重新启动该过程。该技术可以多次处理输入字符串以确定正确的产生式。

  自底向上解析

  顾名思义，自底向上解析从输入符号开始，并尝试构建解析树直到开始符号。

  Example:

  输入字符串：a + b * c

  制作规则：

  
  S → E
  E → E + T
  E → E * T
  E → T
  T → id
  

  让我们开始自底向上解析

  
  a + b * c
  

  读取输入并检查是否有任何产品与输入匹配：

  
  a + b * c
  T + b * c
  E + b * c
  E + T * c
  E * c
  E * T
  E
  S