Python Language
Python Lex-Yacc

Вступление

замечания

Начало работы с 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 также могут быть кортежем строк (а не строки), где каждая строка обозначает токен, как и раньше.

3. Правило регулярных выражений для каждой строки может быть определено как строка или как функция. В любом случае имя переменной должно иметь префикс 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)
     

     4. 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 символов во входной строке.

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

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