Python LanguagePython Lex-Yacc

Вступление

PLY - это реализация на чистом Python популярных инструментов построения компилятора lex и yacc.

замечания

Дополнительные ссылки:

  1. Официальные документы
  2. Github

Начало работы с PLY

Чтобы установить PLY на свой компьютер для python2 / 3, выполните следующие действия:

  1. Загрузите исходный код отсюда .
  2. Разархивируйте загруженный zip-файл
  3. Перейдите в папку с распакованным ply-3.10
  4. Выполните следующую команду в своем терминале: python setup.py install

Если вы закончите все вышеперечисленное, вы должны теперь использовать модуль PLY. Вы можете проверить это, открыв интерпретатор python и набрав import ply.lex .

Примечание: Не используйте pip установить PLY, он установит битый дистрибутив на вашей машине.

«Привет, мир!» PLY - простой калькулятор

Давайте продемонстрируем мощь PLY с помощью простого примера: эта программа примет арифметическое выражение как строковый ввод и попытается его решить.

Откройте свой любимый редактор и скопируйте следующий код:

from ply import lex
import ply.yacc as yacc

tokens = (
    'PLUS',
    'MINUS',
    'TIMES',
    'DIV',
    'LPAREN',
    'RPAREN',
    'NUMBER',
)

t_ignore = ' \t'

t_PLUS    = r'\+'
t_MINUS   = r'-'
t_TIMES   = r'\*'
t_DIV     = r'/'
t_LPAREN  = r'\('
t_RPAREN  = r'\)'

def t_NUMBER( t ) :
    r'[0-9]+'
    t.value = int( t.value )
    return t

def t_newline( t ):
  r'\n+'
  t.lexer.lineno += len( t.value )

def t_error( t ):
  print("Invalid Token:",t.value[0])
  t.lexer.skip( 1 )

lexer = lex.lex()

precedence = (
    ( 'left', 'PLUS', 'MINUS' ),
    ( 'left', 'TIMES', 'DIV' ),
    ( 'nonassoc', 'UMINUS' )
)

def p_add( p ) :
    'expr : expr PLUS expr'
    p[0] = p[1] + p[3]

def p_sub( p ) :
    'expr : expr MINUS expr'
    p[0] = p[1] - p[3]

def p_expr2uminus( p ) :
    'expr : MINUS expr %prec UMINUS'
    p[0] = - p[2]

def p_mult_div( p ) :
    '''expr : expr TIMES expr
            | expr DIV expr'''

    if p[2] == '*' :
        p[0] = p[1] * p[3]
    else :
        if p[3] == 0 :
            print("Can't divide by 0")
            raise ZeroDivisionError('integer division by 0')
        p[0] = p[1] / p[3]

def p_expr2NUM( p ) :
    'expr : NUMBER'
    p[0] = p[1]

def p_parens( p ) :
    'expr : LPAREN expr RPAREN'
    p[0] = p[2]

def p_error( p ):
    print("Syntax error in input!")

parser = yacc.yacc()

res = parser.parse("-4*-(3-5)") # the input
print(res)

Сохраните этот файл как calc.py и запустите его.

Выход:

-8

Какой правильный ответ для -4 * - (3 - 5) .

Часть 1: токенизация ввода с помощью Lex

Существует два этапа выполнения кода из примера 1: один - токенирование ввода, что означает, что он ищет символы, которые составляют арифметическое выражение, а второй - синтаксический анализ , который включает анализ извлеченных токенов и оценку результата.

В этом разделе приведен простой пример того, как вводить токены пользователя, а затем разбивать его по строкам .

    import ply.lex as lex

    # List of token names. This is always required
    tokens = [
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    ]

    # Regular expression rules for simple tokens
    t_PLUS    = r'\+'
    t_MINUS   = r'-'
    t_TIMES   = r'\*'
    t_DIVIDE  = r'/'
    t_LPAREN  = r'\('
    t_RPAREN  = r'\)'

    # A regular expression rule with some action code
    def t_NUMBER(t):
        r'\d+'
        t.value = int(t.value)    
        return t

    # Define a rule so we can track line numbers
    def t_newline(t):
        r'\n+'
        t.lexer.lineno += len(t.value)

    # A string containing ignored characters (spaces and tabs)
    t_ignore  = ' \t'

    # Error handling rule
    def t_error(t):
        print("Illegal character '%s'" % t.value[0])
        t.lexer.skip(1)

    # Build the lexer
    lexer = lex.lex()

    # Give the lexer some input
    lexer.input(data)

    # Tokenize
    while True:
        tok = lexer.token()
        if not tok: 
            break      # No more input
        print(tok)

Сохраните этот файл как calclex.py . Мы будем использовать это при создании нашего анализатора Yacc.


Сломать

  1. Импортируйте модуль с помощью import ply.lex

  2. Все лексеры должны предоставить список, называемый tokens который определяет все возможные имена токенов, которые могут быть созданы лексером. Этот список всегда необходим.

     tokens = [
        'NUMBER',
        'PLUS',
        'MINUS',
        'TIMES',
        'DIVIDE',
        'LPAREN',
        'RPAREN',
     ]
    

tokens также могут быть кортежем строк (а не строки), где каждая строка обозначает токен, как и раньше.

  1. Правило регулярных выражений для каждой строки может быть определено как строка или как функция. В любом случае имя переменной должно иметь префикс t_, чтобы обозначить это правило для сопоставления токенов.

    • Для простых токенов регулярное выражение может быть указано как строки: t_PLUS = r'\+'

    • Если необходимо выполнить какое-либо действие, в качестве функции можно указать правило токена.

         def t_NUMBER(t):
             r'\d+'
             t.value = int(t.value)
             return t
      

      Обратите внимание, что правило задается как строка документа внутри функции. Функция принимает один аргумент, который является экземпляром LexToken , выполняет какое-то действие и затем возвращает аргумент.

      Если вы хотите использовать внешнюю строку в качестве правила регулярного выражения для функции вместо указания строки doc, рассмотрите следующий пример:

         @TOKEN(identifier)         # identifier is a string holding the regex
         def t_ID(t):
             ...      # actions
      
    • Экземпляр объекта LexToken (назовем этот объект t ) имеет следующие атрибуты:

      1. t.type который является типом маркера (как строка) (например: 'NUMBER' , 'PLUS' и т. д.). По умолчанию t.type устанавливается на имя, следующее за префиксом t_ .
      2. t.value который является лексемой (фактический текст соответствует)
      3. t.lineno который является текущим номером строки (это не обновляется автоматически, так как лексер ничего не знает о номерах строк). Обновите lineno, используя функцию t_newline .

        def t_newline(t):
            r'\n+'
            t.lexer.lineno += len(t.value)
      

      1. t.lexpos который является позицией маркера относительно начала входного текста.
    • Если ничего не возвращается из функции правила регулярного выражения, токен отбрасывается. Если вы хотите отменить токен, вы можете вместо этого добавить префикс t_ignore_ к переменной правила regex вместо определения функции для того же правила.

         def t_COMMENT(t):
             r'\#.*'
             pass
             # No return value. Token discarded
      

      ...Такой же как:

         t_ignore_COMMENT = r'\#.*'
      

      Это, конечно, недействительно, если вы выполняете некоторые действия, когда видите комментарий. В этом случае используйте функцию для определения правила регулярного выражения.

      Если вы не определили токен для некоторых символов, но все же хотите его игнорировать, используйте t_ignore = "<characters to ignore>" (эти префиксы необходимы):

         t_ignore_COMMENT = r'\#.*'
         t_ignore  = ' \t'    # ignores spaces and tabs
      

    • При создании главного регулярного выражения lex добавляет регулярные выражения, указанные в файле, следующим образом:

      1. Токены, определенные функциями, добавляются в том же порядке, что и в файле.
      2. Токены, определенные строками, добавляются в порядке убывания длины строки строки, определяющей регулярное выражение для этого токена.

      Если вы соответствуете == и = в том же файле, воспользуйтесь этими правилами.

    • Литералы - это жетоны, которые возвращаются так, как они есть. И t.type и t.value будут установлены самим символом. Определите список литералов как таковых:

      literals = [ '+', '-', '*', '/' ]
      

      или же,

      literals = "+-*/"
      

      Можно записывать функции токена, которые выполняют дополнительные действия при сопоставлении литералов. Однако вам необходимо установить тип токена соответствующим образом. Например:

      literals = [ '{', '}' ]
      
      def t_lbrace(t):
          r'\{'
          t.type = '{'  # Set token type to the expected literal (ABSOLUTE MUST if this is a literal)
          return t
      

    • Обработать ошибки с помощью функции t_error.

      # Error handling rule
      def t_error(t):
          print("Illegal character '%s'" % t.value[0])
          t.lexer.skip(1) # skip the illegal token (don't process it)
      

      В общем случае t.lexer.skip(n) пропускает n символов во входной строке.

  2. Заключительные приготовления:

    Создайте лексер, используя lexer = lex.lex() .

    Вы также можете поместить все внутри класса и вызвать экземпляр класса для определения lexer. Например:

     import ply.lex as lex  
     class MyLexer(object):            
           ...     # everything relating to token rules and error handling comes here as usual 
    
           # Build the lexer
           def build(self, **kwargs):
               self.lexer = lex.lex(module=self, **kwargs)
    
           def test(self, data):
               self.lexer.input(data)
               for token in self.lexer.token():
                   print(token)
    
           # Build the lexer and try it out
    
     m = MyLexer()
     m.build()           # Build the lexer
     m.test("3 + 4")     #
    

    Предоставление ввода с использованием lexer.input(data) где данные являются строкой

    Чтобы получить маркеры, используйте lexer.token() который возвращает маркеры. Вы можете перебирать лексер в цикле, как в:

    for i in lexer: 
        print(i)
    

Часть 2: Анализ токенизированных входных данных с помощью Yacc

В этом разделе объясняется, как обработанный токен из части 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)

Сломать

  • Каждое правило грамматики определяется функцией, где docstring к этой функции содержит соответствующую контекстуальную грамматическую спецификацию. Операторы, составляющие тело функции, реализуют семантические действия правила. Каждая функция принимает один аргумент 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 назначенный в модуле lexer. Таким образом, PLUS будет иметь значение + .

  • Для нетерминалов значение определяется тем, что помещено в p[0] . Если ничего не установлено, значение равно None. Кроме того, p[-1] не совпадает p[3] , так как p не является простым списком ( p[-1] может указывать встроенные действия (здесь не обсуждается)).

Обратите внимание, что функция может иметь любое имя, если она предшествует p_ .

  • p_error(p) определено для улавливания синтаксических ошибок (таких же, как yyerror в yacc / bison).

  • Несколько правил грамматики могут быть объединены в одну функцию, что является хорошей идеей, если постановки имеют сходную структуру.

      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 выполняется в первый раз. Всякий раз, когда возникает конфликт сдвига / уменьшения, парсер всегда сдвигается.