Python开发解析Protobuf文件的简单编译器：PLY实战指南

from ply import lex

# 空格 制表符 回车这些不可见符号都忽略
t_ignore = ' \t\r'

# 解析错误的时候直接抛出异常
def t_error(t):
  raise Exception('error {} at line {}'.format(t.value[0], t.lineno))

# 记录行号，方便出错定位
def t_newline(t):
  r'\n+'
  t.lexer.lineno += len(t.value)

# 支持c++风格的\\注释
def t_ignore_COMMENT(t):
  r'\/\/[^\n]*'

# 变量的命令规则
def t_VARIABLE(t):
  r'[a-z]+'
  return t

# 常数命令规则
def t_CONSTANT(t):
  r'\d+(\.\d+)?'
  t.value = float(t.value)
  return t

# 输入中支持的符号头token，当然也支持t_PLUS = r'\+'的方式将加号定义为token
literals = '+-,;='
tokens = ('VARIABLE', 'CONSTANT')


if __name__ == '__main__':
  data = '''
  -x + 2.4y + z = 0; //this is a comment
  9y - z + 7.2x = -1;
  y - z + x = 8
  '''

  lexer = lex.lex()
  lexer.input(data)
  while True:
    tok = lexer.token()
    if not tok:
      break
    print tok

基于Yacc的语法解析与总结

LexToken(-,'-',2,5)
LexToken(VARIABLE,'x',2,6)
LexToken(+,'+',2,8)
LexToken(CONSTANT,2.4,2,10)
LexToken(VARIABLE,'y',2,13)
LexToken(+,'+',2,15)
LexToken(VARIABLE,'z',2,17)
LexToken(=,'=',2,19)
LexToken(CONSTANT,0.0,2,21)
LexToken(;,';',2,22)```

### 语法解析

ply中的yacc用作语法分析，虽然复杂的词法分析可以代替简单的语法分析，但类似于编程语言的解析再复杂的词法分析也胜任不了。在使用yacc之前，需要了解上下文无关文法，这部分内容太多太杂，我也只了解部分简单的概念，有兴趣的可以看一看编译原理深入了解。

目前语法分析的方法有两大类，即自下向上的分析方法和自上而下的分析方法。所谓自上而下的分下法就是从文法的开始符号出发，根据文法规则正向推到出给定句子的一种方法，或者说，从树根开始，往下构造语法树，直到建立每个树叶的分析方法。代表算法是LL(1)，此算法文法解析能力不强，对文法定义要求比较高，主流的编译器都没有使用。自下而上的分析法是从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法的开始符号，或者说从语法书的末端开始，步步向上归约，直至归约到根节点的分析方法。代表算法有SLR、LRLR，ply使用的就是LRLR。

因此我们只需要定义文法和规约动作即可，以下就是完整的代码。

```python
# -*- coding=utf8 -*-

from ply import (
  lex,
  yacc
)

# 空格 制表符 回车这些不可见符号都忽略
t_ignore = ' \t\r'

# 解析错误的时候直接抛出异常
def t_error(t):
  raise Exception('error {} at line {}'.format(t.value[0], t.lineno))

# 记录行号，方便出错定位
def t_newline(t):
  r'\n+'
  t.lexer.lineno += len(t.value)

# 支持c++风格的\\注释
def t_ignore_COMMENT(t):
  r'\/\/[^\n]*'

# 变量的命令规则
def t_VARIABLE(t):
  r'[a-z]+'
  return t

# 常数命令规则
def t_CONSTANT(t):
  r'\d+(\.\d+)?'
  t.value = float(t.value)
  return t

# 输入中支持的符号头token，当然也支持t_PLUS = r'\+'的方式将加号定义为token
literals = '+-,;='
tokens = ('VARIABLE', 'CONSTANT')

# 顶层文法，规约的时候equations对应的p[1]是一个列表，包含了方程左边各个变量与系数还有方程左边的常数
def p_start(p):
  """start : equations"""
  var_count, var_list = 0, []
  for left, _ in p[1]:
    for con, var_name in left:
      if var_name in var_list:
        continue
      var_list.append(var_name)
      var_count += 1

  matrix = [[0] * (var_count + 1) for _ in xrange(len(p[1]))]
  for counter, eq in enumerate(p[1]):
    left, right = eq
    for con, var_name in left:
      matrix[counter][var_list.index(var_name)] = con
    matrix[counter][-1] = -right

  var_list.append(1)
  p[0] = matrix, var_list

# 方程组对应的文法，每个方程用，或者；做分隔
def p_equations(p):
  """equations : equation ',' equations
         | equation ';' equations
         | equation"""
  if len(p) == 2:
    p[0] = [p[1]]
  else:
    p[0] = [p[1]] + p[3]

# 单个方程对应的文法
def p_equation(p):
  """equation : eq_left '=' eq_right"""
  p[0] = (p[1], p[3])

# 方程等式左边对应的文法
def p_eq_left(p):
  """eq_left : var_unit eq_left
        |"""
  if len(p) == 1:
    p[0] = []
  else:
    p[0] = [p[1]] + p[2]

# 六种文法对应例子： x, 5x, +x, -x, +4x, -4y
# 归约的形式是一个元组，例： (5, 'x')
def p_var_unit(p):
  """var_unit : VARIABLE
        | CONSTANT VARIABLE
        | '+' VARIABLE
        | '-' VARIABLE
        | '+' CONSTANT VARIABLE
        | '-' CONSTANT VARIABLE"""
  len_p = len(p)
  if len_p == 2:
    p[0] = (1.0, p[1])
  elif len_p == 3:
    if p[1] == '+':
      p[0] = (1.0, p[2])
    elif p[1] == '-':
      p[0] = (-1.0, p[2])
    else:
      p[0] = (p[1], p[2])
  else:
    if p[1] == '+':
      p[0] = (p[2], p[3])
    else:
      p[0] = (-p[2], p[3])

# 方程等式右边对应的常数，对应的例子：1.2， +1.2， -1.2
def p_eq_right(p):
  """eq_right : CONSTANT
        | '+' CONSTANT
        | '-' CONSTANT"""
  if len(p) == 3:
    if p[1] == '-':
      p[0] = -p[2]
    else:
      p[0] = p[2]
  else:
    p[0] = p[1]

if __name__ == '__main__':
  data = '''
  -x + 2.4y + z = 0; //this is a comment
  9y - z + 7.2x = -1;
  y - z + x = 8
  '''

  lexer = lex.lex()
  parser = yacc.yacc(debug=True)
  lexer.lineno = 1
  s = parser.parse(data)
  print s