gpt4 book ai didi

python - PLY:需要帮助理解 LALR 解析器如何解析给定语法的输入

转载 作者:行者123 更新时间:2023-12-01 08:01:02 27 4
gpt4 key购买 nike

我正在使用 PLY python 包为 C 的子集构建前端编译器,但我仍然在努力理解自下而上的解析器(特别是 LALR)是如何工作的。我用给定的语法编写了一个简单的程序来看看它是如何工作的:

expression -> vowel_list consonant_list

vowel_list -> VOWEL vowel_list
| VOWEL

consonant_list : CONSONANT consonant_list
| CONSONANT

并使用输入字符串:'EUAIOTNC'

作为不同语法规则的操作,我使用一个列表,在其中附加解析器看到的所有标记。基本上,当减少发生时, token 会被附加到列表中。解析结束时,获得起始符号表达式时,列表显示:['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 解析器如何解析我的输入?

最佳答案

它正在像你告诉它的那样解析它。当你说:

vowel_list: VOWEL vowel_list

你说的是:

  1. 识别元音

  2. 完全处理 vowel_list(包括执行该 vowel_list 的缩减操作)。

  3. 最后,为此vowel_list执行相关的缩减操作。

很明显为什么这会导致从右到左打印VOWEL。第一个 VOWEL 打印在最外层 vowel_list 的缩减操作中,仅在所有内部 vowel_list 的缩减操作之后执行。

如果您以自下而上解析的正常方式编写语法,使用左递归,则操作将产生您期望的打印顺序:

vowel_list: vowel_list VOWEL

实际上,该语法意味着“要识别元音列表,首先识别较短的元音列表,然后添加另一个元音。”

这一切都与 LALR 算法无关。它是您编写的语法中固有的。任何在产生式完成时执行操作的解析器必然会采取相同的行为。这确实是执行操作的唯一合理时间,因为通常每个操作都依赖于了解与其组件相关的计算。

LR 算法的重要之处在于它们允许解析左递归语法,从而允许您使用自然执行顺序。如果您要在规则中间注入(inject)一个操作,或者使用其自己的单独操作将每个 VOWEL 封装在一个单元产生式中,则只能使用右递归规则来执行此操作。

关于python - PLY:需要帮助理解 LALR 解析器如何解析给定语法的输入,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55731396/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com