第 2 部分使用 Yacc 解析标记化输入

Created: November-22, 2018

本节介绍如何处理第 1 部分中的标记化输入 - 使用 Context Free Grammars(CFG) 完成。必须指定语法，并根据语法处理标记。在引擎盖下，解析器使用 LALR 解析器。

# Yacc example

import ply.yacc as yacc

# Get the token map from the lexer. This is required.
from calclex import tokens

def p_expression_plus(p):
    'expression : expression PLUS term'
    p[0] = p[1] + p[3]

def p_expression_minus(p):
    'expression : expression MINUS term'
    p[0] = p[1] - p[3]

def p_expression_term(p):
    'expression : term'
    p[0] = p[1]

def p_term_times(p):
    'term : term TIMES factor'
    p[0] = p[1] * p[3]

def p_term_div(p):
    'term : term DIVIDE factor'
    p[0] = p[1] / p[3]

def p_term_factor(p):
    'term : factor'
    p[0] = p[1]

def p_factor_num(p):
    'factor : NUMBER'
    p[0] = p[1]

def p_factor_expr(p):
    'factor : LPAREN expression RPAREN'
    p[0] = p[2]

# Error rule for syntax errors
def p_error(p):
    print("Syntax error in input!")

# Build the parser
parser = yacc.yacc()

while True:
   try:
       s = raw_input('calc > ')
   except EOFError:
       break
   if not s: continue
   result = parser.parse(s)
   print(result)

分解

每个语法规则由一个函数定义，其中该函数的文档字符串包含适当的无上下文语法规范。构成函数体的语句实现规则的语义动作。每个函数接受单个参数 p，该参数是包含相应规则中每个语法符号的值的序列。p[i] 的值映射到语法符号，如下所示：
```
  def p_expression_plus(p):
      'expression : expression PLUS term'
      #   ^            ^        ^    ^
      #  p[0]         p[1]     p[2] p[3]

      p[0] = p[1] + p[3]
```
对于标记，相应 p[i] 的值与词法模块中分配的 p.value 属性相同。所以，PLUS 将具有+的价值。
对于非终端，该值由 p[0] 中的任何内容确定。如果未放置任何内容，则值为 None。此外，p[-1] 与 p[3] 不同，因为 p 不是一个简单的列表（p[-1] 可以指定嵌入式动作（这里不讨论））。

请注意，该函数可以具有任何名称，只要它在 p_ 之前。

定义 p_error(p) 规则以捕获语法错误（与 yacc / bison 中的 yyerror 相同）。

多个语法规则可以组合成一个单独的函数，如果制作具有类似的结构，这是一个好主意。

  def p_binary_operators(p):
      '''expression : expression PLUS term
                    | expression MINUS term
         term       : term TIMES factor
                    | term DIVIDE factor'''
      if p[2] == '+':
          p[0] = p[1] + p[3]
      elif p[2] == '-':
          p[0] = p[1] - p[3]
      elif p[2] == '*':
          p[0] = p[1] * p[3]
      elif p[2] == '/':
          p[0] = p[1] / p[3]

可以使用字符文字代替标记。

  def p_binary_operators(p):
      '''expression : expression '+' term
                    | expression '-' term
         term       : term '*' factor
                    | term '/' factor'''
      if p[2] == '+':
          p[0] = p[1] + p[3]
      elif p[2] == '-':
          p[0] = p[1] - p[3]
      elif p[2] == '*':
          p[0] = p[1] * p[3]
      elif p[2] == '/':
          p[0] = p[1] / p[3]

当然，必须在词法分析器模块中指定文字。

空作品的形式为'''symbol : '''
要明确设置起始符号，请使用 start = 'foo'，其中 foo 是非终端符号。

可以使用优先级变量来设置优先级和关联性。

  precedence = (
      ('nonassoc', 'LESSTHAN', 'GREATERTHAN'),  # Nonassociative operators
      ('left', 'PLUS', 'MINUS'),
      ('left', 'TIMES', 'DIVIDE'),
      ('right', 'UMINUS'),            # Unary minus operator
  )

令牌从最低到最高排序。nonassoc 意味着那些令牌不相关。这意味着像 a < b < c 这样的东西是非法的，而 a < b 仍然是合法的。

parser.out 是第一次执行 yacc 程序时创建的调试文件。每当发生移位/减少冲突时，解析器总是移位。