第 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 程式時建立的除錯檔案。每當發生移位/減少衝突時，解析器總是移位。