from ply import lex

# 空格 制表符 回車(chē)這些不可見(jiàn)符號(hào)都忽略
t_ignore = ' \t\r'

# 解析錯(cuò)誤的時(shí)候直接拋出異常
def t_error(t):
  raise Exception('error {} at line {}'.format(t.value[0], t.lineno))

# 記錄行號(hào)，方便出錯(cuò)定位
def t_newline(t):
  r'\n+'
  t.lexer.lineno += len(t.value)

# 支持c++風(fēng)格的\\注釋
def t_ignore_COMMENT(t):
  r'\/\/[^\n]*'

# 變量的命令規(guī)則
def t_VARIABLE(t):
  r'[a-z]+'
  return t

# 常數(shù)命令規(guī)則
def t_CONSTANT(t):
  r'\d+(\.\d+)?'
  t.value = float(t.value)
  return t

# 輸入中支持的符號(hào)頭token，當(dāng)然也支持t_PLUS = r'\+'的方式將加號(hào)定義為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

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)```

### 語(yǔ)法解析

ply中的yacc用作語(yǔ)法分析，雖然復(fù)雜的詞法分析可以代替簡(jiǎn)單的語(yǔ)法分析，但類似于編程語(yǔ)言的解析再?gòu)?fù)雜的詞法分析也勝任不了。在使用yacc之前，需要了解上下文無(wú)關(guān)文法，這部分內(nèi)容太多太雜，我也只了解部分簡(jiǎn)單的概念，有興趣的可以看一看編譯原理深入了解。

目前語(yǔ)法分析的方法有兩大類，即自下向上的分析方法和自上而下的分析方法。所謂自上而下的分下法就是從文法的開(kāi)始符號(hào)出發(fā)，根據(jù)文法規(guī)則正向推到出給定句子的一種方法，或者說(shuō)，從樹(shù)根開(kāi)始，往下構(gòu)造語(yǔ)法樹(shù)，直到建立每個(gè)樹(shù)葉的分析方法。代表算法是LL(1)，此算法文法解析能力不強(qiáng)，對(duì)文法定義要求比較高，主流的編譯器都沒(méi)有使用。自下而上的分析法是從給定的輸入串開(kāi)始，根據(jù)文法規(guī)則逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)，或者說(shuō)從語(yǔ)法書(shū)的末端開(kāi)始，步步向上歸約，直至歸約到根節(jié)點(diǎn)的分析方法。代表算法有SLR、LRLR，ply使用的就是LRLR。

因此我們只需要定義文法和規(guī)約動(dòng)作即可，以下就是完整的代碼。

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

from ply import (
  lex,
  yacc
)

# 空格 制表符 回車(chē)這些不可見(jiàn)符號(hào)都忽略
t_ignore = ' \t\r'

# 解析錯(cuò)誤的時(shí)候直接拋出異常
def t_error(t):
  raise Exception('error {} at line {}'.format(t.value[0], t.lineno))

# 記錄行號(hào)，方便出錯(cuò)定位
def t_newline(t):
  r'\n+'
  t.lexer.lineno += len(t.value)

# 支持c++風(fēng)格的\\注釋
def t_ignore_COMMENT(t):
  r'\/\/[^\n]*'

# 變量的命令規(guī)則
def t_VARIABLE(t):
  r'[a-z]+'
  return t

# 常數(shù)命令規(guī)則
def t_CONSTANT(t):
  r'\d+(\.\d+)?'
  t.value = float(t.value)
  return t

# 輸入中支持的符號(hào)頭token，當(dāng)然也支持t_PLUS = r'\+'的方式將加號(hào)定義為token
literals = '+-,;='
tokens = ('VARIABLE', 'CONSTANT')

# 頂層文法，規(guī)約的時(shí)候equations對(duì)應(yīng)的p[1]是一個(gè)列表，包含了方程左邊各個(gè)變量與系數(shù)還有方程左邊的常數(shù)
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

# 方程組對(duì)應(yīng)的文法，每個(gè)方程用，或者；做分隔
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]

# 單個(gè)方程對(duì)應(yīng)的文法
def p_equation(p):
  """equation : eq_left '=' eq_right"""
  p[0] = (p[1], p[3])

# 方程等式左邊對(duì)應(yīng)的文法
def p_eq_left(p):
  """eq_left : var_unit eq_left
        |"""
  if len(p) == 1:
    p[0] = []
  else:
    p[0] = [p[1]] + p[2]

# 六種文法對(duì)應(yīng)例子： x, 5x, +x, -x, +4x, -4y
# 歸約的形式是一個(gè)元組，例： (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])

# 方程等式右邊對(duì)應(yīng)的常數(shù)，對(duì)應(yīng)的例子：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