[Python] PLY (Python Lex-Yacc) 정리 - Yacc

Lexer 에 대한 내용은 Lex 정리 문서 를 참조 해주세요.

2. parse

• 언어 문법을 파싱하기 위해서 yacc.py 를 이용한다.
  • YACC(Yet Another Compiler Compiler) 은 LR-parsing / shift-reduce parsing 으로 알려진 분석 기술을 사용한다.
  • LR-parsing
    • 입력 기호들을 읽어가면서 기호들을 reduce 하여 시작 기호로 반환되는 상향식(bottom-up) 구문 분석 기법이다.
    • stack 과 input buffer 를 이용해서 분석이 가능하다
    • 참고링크 : https://en.wikipedia.org/wiki/LR_parser
• syntax 는 BNF(Backers Naur From) 구문으로 표기한다.
  • 예를 들어, 간단한 산술 계산식을 분석 하려고 할 때, 아래와 같이 모호하지 않은(unambiguous) 문법을 BNF 구문으로 규정해야 한다.

  expression : expression + term
             | expression - term
             | term
  
  term       : term * factor
             | term / factor
             | factor
  
  factor     : NUMBER
             | ( expression )

2.1. 사용 예제

import ply.yacc as yacc

# lexer 를 통해서 만들어진 token 들을 가져온다.
from calclex import tokens

# p 로 각 symbol 이 할당되고, 0 부터 시작하는 index 로 각 symbol 을 선택 할 수 있다.
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
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)

2.2. Combining Grammar Rule Functions

• 비슷한 rule 을 가진 여러 함수를 하나의 함수로 합칠 수 있다.

# 각각 함수에 rule 이 존재 하지만, 구조는 비슷하다.
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(p):
  '''expression : expression PLUS term
                | expression MINUS term'''
  if p[2] == '+':
    p[0] = p[1] + p[3]
  elif p[2] == '-':
    p[0] = p[1] - p[3]

2.3. Character Literals

• 문자 하나 를 그대로 symbol 로 사용 할 수 있다.
• lex 에 literals 로 지정이 된 경우에만 사용 가능하다.

# lex 파일
literals = ['+','-','*','/' ]

# parse
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]

2.4. Empty Productions

• yacc.py 는 empty rule 을 처리 할 수 있다.

def p_empty(p):
  'empty :'
  pass

2.5. Changing the starting symbol

• 일반적으로 가장 위에 정의된 문법 rule 이 yacc 의 시작 점이 된다.
• 이것을 바꾸기 위해서는 start 변수로 특정하면 된다.

start = 'foo'

def p_bar(p):
  'bar : A B'

# This is the starting rule due to the start specifier above
def p_foo(p):
  'foo : bar X'
  ...

• 이 기술을 large rule set 에서 부분만 체크 하고 싶을 때 사용 할 수 있다.

parser = yacc.yacc(start='foo')

2.6. Dealing With Ambiguous Grammars

• 완벽하게 잘 정의된 문법을 작성하는 것은 쉽지 않다.
• 그렇기 때문에 대부분의 경우 모호한(ambiguous) 문법을 작성하는 경우가 생긴다.
  • 예를 들어) 3 * 4 + 5 에서는 우선순위를 알 수 없다.
• 모호한 문법이 전달되면 yacc 에서는 shift/reduce conflicts / reduce/reduce conflicts 메세지가 출력된다.

2.6.1. shift/reduce conflicts

• shift symbol 과 reduce 동작에서 분석기가 결정하지 못 할 때 발생한다.
• 이것을 다루기 위해서 yacc.py 에서는 우선순위를 지정 할 수 있도록 precedence 변수를 지원한다.
  • 우선순위는 bottom -> top 으로 정의된다.
  • 아래 예제에서는 TIMES/DIVIDE 가 우선순위가 높다.

precedence = (
  ('left', 'PLUS', 'MINUS'),  # PLUS/MINUS 는 같은 우선순위를 가진다. 왼쪽으로 연관성이 있다.
  ('left', 'TIMES', 'DIVIDE'),  # TIMES/DIVIDE 는 같은 우선순위를 가진다. 왼쪽으로 연관성이 있다.
)

# 아래와 같은 우선순위를 가진다.
PLUS      : level = 1,  assoc = 'left'
MINUS     : level = 1,  assoc = 'left'
TIMES     : level = 2,  assoc = 'left'
DIVIDE    : level = 2,  assoc = 'left'

# 예제 문법
expression : expression PLUS expression                 # level = 1, left
           | expression MINUS expression                # level = 1, left
           | expression TIMES expression                # level = 2, left
           | expression DIVIDE expression               # level = 2, left
           | LPAREN expression RPAREN                   # level = None (not specified)
           | NUMBER                                     # level = None (not specified)

• unary-minus operation 의 경우 우선순위가 가장 높기 때문에 아래와 같이 표현 될 수 있다.

precedence = (
  ('left', 'PLUS', 'MINUS'),
  ('left', 'TIMES', 'DIVIDE'),
  ('right', 'UMINUS'),            # Unary minus operator
)

# %prec UMINUS 문법을 이용해서 기본 우선순위 세팅을 UMINUS 로 변경한다
def p_expr_uminus(p):
  'expression : MINUS expression %prec UMINUS'
  p[0] = -p[2]

• 우선순위 지정을 통해서 비연관적인 (non-associativity) 것을 지정 할 수 있다.
  • 예를 들어, 비교연산자 (< , >) 동작을 정의 하력 하는데 a < b < c 같은 문법은 지원하고 싶지 않는 경우에 사용 할 수 있다

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

2.6.2. reduce/reduce conflicts

• 주어진 symbol 에 대한 여러 문법이 존재하는 경우에 발생된다.

assignment :  ID EQUALS NUMBER
           |  ID EQUALS expression

expression : expression PLUS expression
           | expression MINUS expression
           | expression TIMES expression
           | expression DIVIDE expression
           | LPAREN expression RPAREN
           | NUMBER

• 이 문제가 발생할 때 아래와 같은 로그를 통해서 어느 부분이 모호한지 확인 할 수 있다.

WARNING: 1 reduce/reduce conflict
WARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER)
WARNING: rejected rule (expression -> NUMBER)

2.7. Syntax Error Handling

• PLY 문서의 [6.8 Syntax Error Handling] 참조

Reference

• PLY 문서 : https://www.dabeaz.com/ply/ply.html