PLY: нужна помощь в понимании того, как синтаксический анализатор LALR анализирует входные данные для моей заданной грамматики - PullRequest
Новая
       43

PLY: нужна помощь в понимании того, как синтаксический анализатор LALR анализирует входные данные для моей заданной грамматики

1 голос
/ 17 апреля 2019

Я использую пакет PLY python для создания внешнего компилятора для подмножества C, но я все еще пытаюсь понять, как работает анализатор снизу вверх (в частности, LALR). Я написал простую программу с заданной грамматикой, чтобы увидеть, как все работает: 

expression -> vowel_list consonant_list

vowel_list -> VOWEL vowel_list
        | VOWEL

consonant_list : CONSONANT consonant_list
            | CONSONANT

И использовал входную строку: 'EUAIOTNC'

В качестве действия для различных правил грамматики я использую список, в который я добавляю все токены, которые видит анализатор. По сути, токен добавляется в список, когда происходит сокращение. В конце синтаксического анализа, когда получено выражение начального символа, список выглядит так: ['O', 'I', 'A', 'U', 'E', 'C', 'N', 'T'] . 

import ply.lex as lex
import ply.yacc as yacc
tokens = ['VOWEL','CONSONANT']

t_VOWEL = r'[AEIOUaeiou]'
t_CONSONANT = r'[A-Za-z]'

def t_error(token):
    print(f'Illegal character: {token.value} on line number {t.lineno}')
    token.lexer.skip(1)

def t_whitespace(t):
    r'\s+'
    pass

lexer = lex.lex()

tokens_generated = []

def p_expression(p):
    '''
    expression : vowel_list consonant_list
    '''

    print(p.stack)
    print('Derivation complete!')
    print(f'The tokens generated are: {tokens_generated}')


def p_vowel_list(p):
    '''
    vowel_list : VOWEL vowel_list
                | VOWEL
    '''
    print(f'Derived the vowel {p[1]} !')
    tokens_generated.append(p[1])

def p_consonant_list(p):
    '''
    consonant_list : CONSONANT consonant_list
                    | CONSONANT
    '''
    print(f'Derived the consonant {p[1]}!')
    tokens_generated.append(p[1])


def p_error(p):
    if p == None:
        token = "end of file"
    else:
        token = f"{p.type}({p.value}) on line {p.lineno}"

input_string = 'EUAIOTNC'

parser = yacc.yacc(method='LALR',debug=True)
parser.parse(input_string)

Вывод, который я получаю: 

Derived the vowel O !
Derived the vowel I !
Derived the vowel A !
Derived the vowel U !
Derived the vowel E !
Derived the consonant C!
Derived the consonant N!
Derived the consonant T!
[$end]
Derivation complete!
The tokens generated are: ['O', 'I', 'A', 'U', 'E', 'C', 'N', 'T']

Я не могу понять, как это происходит. Я ожидал, что список будет содержать токены в том же порядке, что и в строке. Может кто-нибудь объяснить, почему я получаю то, что получаю? Как синтаксический анализатор LALR анализирует мой ввод?

1 Ответ

1 голос
/ 17 апреля 2019

Он разбирает это, как вы сказали. Когда вы говорите: 

vowel_list: VOWEL vowel_list

что вы говорите:

  1. Распознать VOWEL.

  2. Полностью обработать vowel_list (что включает в себя выполнение действия сокращения vowel_list).

  3. Наконец, выполните соответствующее действие сокращения для этого vowel_list.

Должно быть понятно, почему это приводит к печати VOWEL справа налево. Первый VOWEL печатается в самом внешнем vowel_list сокращающем действии, которое выполняется только после всех внутренних vowel_list s уменьшающих действий.

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

vowel_list: vowel_list VOWEL

По сути, эта грамматика означает «распознать vowel_list, сначала распознать более короткий vowel_list, а затем добавить еще один VOWEL».

Ничто из этого не имеет отношения к алгоритму LALR. Это присуще написанной вами грамматике. Любой синтаксический анализатор, который выполняет действия после завершения производства, обязательно будет действовать так же. И это действительно единственное разумное время для выполнения действия, потому что обычно каждое действие зависит от знания вычислений, связанных с его компонентами.

Что важно в алгоритмах LR, так это то, что они позволяют анализировать леворекурсивные грамматики, позволяя вам использовать естественный порядок выполнения. Вы могли бы сделать это только с помощью праворекурсивного правила, если бы вы должны были вставить действие в середину правила или инкапсулировать каждый VOWEL в единичном производстве с помощью своего отдельного действия.

...