Нормализация структурные различия в грамматике

Question

Рассмотрим следующую грамматику:

S → A | B 
A → xy 
B → xyz 

Это то, что я думаю, что LR (0) парсер сделать данный вход xyz:

| xyz → shift 
    x | yz → shift 
xy | z  → reduce 
    A | z  → shift 
Az |  → fail 

Если мое предположение верно и мы изменили правила B следующим образом:

B → Az 

сейчас грамматика внезапно становится приемлемой парсером LR (0). Я предполагаю, что эта новая грамматика описывает тот же самый набор строк, что и первая грамматика в этом вопросе.

• В чем разница между первой и второй грамматиками?
• Как мы отделяем структурные различия в наших грамматиках от языка, который они описывают?
  • Через нормализацию?
  • Какая нормализация?

Для дальнейшего уточнения:

Я хочу описать язык синтаксического анализатора, без структуры грамматики играет определенную роль. Я хотел бы получить самое минимальное/фундаментальное описание набора строк. Для грамматик LR (k) я хотел бы свести к минимуму k.

Answer 1

Я думаю, что ваш LR(0) анализатор не является стандартным анализатор:

• Source

LR (0) Анализатор представляет собой сдвиг/свертка анализатор, который использует нулевые маркеры из опережающего просмотра, чтобы определить, какое действие нужно предпринять (следовательно, 0). Это означает, что в любой конфигурации анализатора парсер должен иметь однозначное действие для выбора - либо он сдвигает определенный символ, либо применяет конкретное сокращение. Если есть два или более вариантов, парсер терпит неудачу, и мы говорим, что грамматика не LR (0).

Итак, когда у вас есть:

S->A|B 
A->xy 
B->Az 

или

S->A|B 
A->xy 
B->xyz 

LR(0) никогда не будет проверять B правило, и для них обоих это не удастся.

State0 - Clousure(S->°A): 
    S->°A 
    A->°xy 

Arcs: 
    0 --> x --> 2 
    0 --> A --> 1 
------------------------- 

State1 - Goto(State0,A): 
    S->A° 

Arcs: 
    1 --> $ --> Accept 
------------------------- 

State2 - Goto(State0,x): 
    A->x°y 

Arcs: 
    2 --> y --> 3 
------------------------- 

State3 - Goto(State2,y): 
    A->xy° 

Arcs: 
------------------------- 

Но если у вас есть

I->S 
S->A|B 
A->xy 
B->xyz       or B->Az 

Оба из них будут принимать xyz, но в отличие гласит:

State0 - Clousure(I->°S): 
    I->°S 
    S->°A 
    S->°B 
    A->°xy       A->°xy, $z 
    B->°xyz       B->°Az, $ 

Arcs: 
    0 --> x --> 4 
    0 --> S --> 1 
    0 --> A --> 2 
    0 --> B --> 3 
------------------------- 

State1 - Goto(State0,S): 
    I->S° 

Arcs: 
    1 --> $ --> Accept 
------------------------- 

State2 - Goto(State0,A): 
    S->A°       S->A°, $ 
            B->A°z, $ 
Arcs:        2 --> z --> 5 
------------------------- 

State3 - Goto(State0,B): 
    S->B° 

Arcs: 
------------------------- 

State4 - Goto(State0,x): 
    A->x°y       A->x°y, $z 
    B->x°yz 

Arcs: 
    4 --> y --> 5      4 --> y --> 6 
------------------------- 

State5 - Goto(State4,y):   - Goto(State2,z): 
    A->xy°       B->Az°, $ 

Arcs: 
    5 --> z --> 6      -<None>- 
------------------------- 

State6 - Goto(State5,z):   - Goto(State4,y) 
    B->xyz°       A->xy°, $z 

Arcs: 
------------------------- 

Вы можете увидеть Goto Table и Action Table отличается.

[B->xyz]         [B->Az] 
    | Stack | Input | Action    | Stack | Input | Action 
--+---------+--------+----------   --+---------+--------+---------- 
1 | 0  | xyz$ | Shift    1 | 0  | xyz$ | Shift 
2 | 0 4  | yz$ | Shift    2 | 0 4  | xy$ | Shift 
3 | 0 4 5 | z$  | Shift    3 | 0 4 6 | z$  | Reduce A->xy 
4 | 0 4 5 6 | $  | Reduce B->xyz  4 | 0 2  | z$  | Shift 
5 | 0 3  | $  | Reduce S->B  5 | 0 2 5 | $  | Reduce B->Az 
6 | 0 1  | $  | Accept    6 | 0 3  | $  | Reduce S->B 
              7 | 0 1  | $  | Accept 

Просто при изменении B->xyz к B->Az добавлении Action к вашему LR Table найти различия, вы можете проверить Action Table и Goto Table (Constructing LR(0) parsing tables)

• Если у вас есть A->xy и B->xyz то у вас есть две нижние ручки [xy или xyz], но когда у вас есть B->Az, у вас есть только одна нижняя ручка [xy], который может принять дополнительно z.

• Я думаю, что касается локальной оптимизации -c = a + b; d = a + b -> c = a + b; d = c- если вы используете B->Az, вы делаете B->xyz оптимизированным.