Что такое замыкание леворекурсивного элемента LR(0) с эпсилон-переходами?

Допустим, у меня есть эта грамматика:

A: ε
 | B 'a'
B: ε
 | B 'b'

Что считается замыканием элемента A: • B 'a'?
Другими словами, как мне работать с эпсилон-переходами при вычислении замыканий?


parsing language-agnostic grammar lr epsilon
person user541686    schedule 19.10.2012    source источник
comment
Аналогичный вопрос для парсера LR(1): парсер LR1 и Epsilon   -  person Markus Jarderot    schedule 27.10.2012

Ответы (1)


arrow_upward
5
arrow_downward

Это довольно просто. Входит в состав закрытия

    A = ... <dot> X ... ;

все правила

    X =   <dot> R1 R2 R3 ... ;

где first(R1) не пусто. Для каждого (непустого) токена K в первом (R1) вам нужно (транзитивно!) включить

    R1 = <dot> k ... ;

и т. д., но, по-видимому, вы уже поняли это.

Ваш конкретный вопрос: что произойдет, если R1 может быть пустым? Тогда вам также нужно включить

    X =   R1 <dot> R2 ... ;

Аналогично для пустого R2, если R1 может быть пустым, и аналогично для Ri пустого, если R1 .. Ri-1 может быть пустым. В экстремальных обстоятельствах все Ri могут быть пустыми (множество необязательных подпунктов в вашей грамматике), и вы можете в конечном итоге включить

    X =  R1 R2 ... Rn <dot> ;

Обратите внимание, что определение того, что first(R1) «может быть пустым», само по себе является вопросом транзитивного закрытия.

Генератор синтаксического анализатора GLR, который я создал для DMS, предварительно вычисляет first_can_be_empty, используя алгоритм Уоршалла, а затем использует его в построении замыкания.

person Ira Baxter    schedule 29.10.2012
comment
Ха, интересно... уточнить, под Уоршаллом ты подразумеваешь Флойда-Уоршалла? то есть алгоритм кратчайших путей для всех пар? - person user541686; 29.10.2012
comment
Да, но вам не нужен кратчайший путь, достаточно существования пути, так что вы можете сделать все это с помощью битов, а затем вы поймете, что можете сделать это с помощью битовых векторов для довольно значительного ускорения. - person Ira Baxter; 29.10.2012