上記の回答に加えて、ボトムアップ LR パーサーのクラスの個々のパーサー間の違いは、解析テーブルを生成するときにシフト/リデュースまたはリデュース/リデュースの競合が発生するかどうかです。競合が少ないほど、文法はより強力になります (LR(0) < SLR(1) < LALR(1) < CLR(1))。
たとえば、次の式の文法を考えてみましょう。
E → E + T
え→た
T→F
T → T * F
へ → ( へ )
F→id
LR(0) ではなく SLR(1) です。次のコードを使用して、LR0 オートマトンを構築し、解析テーブルを構築できます (文法を拡張し、クロージャを使用して DFA を計算し、アクションを計算してセットに移動する必要があります)。
from copy import deepcopy
import pandas as pd
def update_items(I, C):
if len(I) == 0:
return C
for nt in C:
Int = I.get(nt, [])
for r in C.get(nt, []):
if not r in Int:
Int.append(r)
I[nt] = Int
return I
def compute_action_goto(I, I0, sym, NTs):
#I0 = deepcopy(I0)
I1 = {}
for NT in I:
C = {}
for r in I[NT]:
r = r.copy()
ix = r.index('.')
#if ix == len(r)-1: # reduce step
if ix >= len(r)-1 or r[ix+1] != sym:
continue
r[ix:ix+2] = r[ix:ix+2][::-1] # read the next symbol sym
C = compute_closure(r, I0, NTs)
cnt = C.get(NT, [])
if not r in cnt:
cnt.append(r)
C[NT] = cnt
I1 = update_items(I1, C)
return I1
def construct_LR0_automaton(G, NTs, Ts):
I0 = get_start_state(G, NTs, Ts)
I = deepcopy(I0)
queue = [0]
states2items = {0: I}
items2states = {str(to_str(I)):0}
parse_table = {}
cur = 0
while len(queue) > 0:
id = queue.pop(0)
I = states[id]
# compute goto set for non-terminals
for NT in NTs:
I1 = compute_action_goto(I, I0, NT, NTs)
if len(I1) > 0:
state = str(to_str(I1))
if not state in statess:
cur += 1
queue.append(cur)
states2items[cur] = I1
items2states[state] = cur
parse_table[id, NT] = cur
else:
parse_table[id, NT] = items2states[state]
# compute actions for terminals similarly
# ... ... ...
return states2items, items2states, parse_table
states, statess, parse_table = construct_LR0_automaton(G, NTs, Ts)
ここで、文法 G、非終端記号および終端記号は次のように定義されます
G = {}
NTs = ['E', 'T', 'F']
Ts = {'+', '*', '(', ')', 'id'}
G['E'] = [['E', '+', 'T'], ['T']]
G['T'] = [['T', '*', 'F'], ['F']]
G['F'] = [['(', 'E', ')'], ['id']]
上記の LR(0) 解析テーブル生成用に実装した便利な関数を次にいくつか示します。
def augment(G, S): # start symbol S
G[S + '1'] = [[S, '$']]
NTs.append(S + '1')
return G, NTs
def compute_closure(r, G, NTs):
S = {}
queue = [r]
seen = []
while len(queue) > 0:
r = queue.pop(0)
seen.append(r)
ix = r.index('.') + 1
if ix < len(r) and r[ix] in NTs:
S[r[ix]] = G[r[ix]]
for rr in G[r[ix]]:
if not rr in seen:
queue.append(rr)
return S
次の図 (展開して表示) は、上記のコードを使用して文法用に構築された LR0 DFA を示しています。
次の表は、pandas データフレームとして生成された LR(0) 解析テーブルを示しています。文法が LR(0) ではないことを示すシフト/リデュースの競合がいくつかあることに注意してください。
SLR(1) パーサーは、次の入力トークンが還元される非終端記号のフォロー セットのメンバーである場合にのみ還元することで、上記のシフト/還元の競合を回避します。次の解析テーブルは、SLR によって生成されます。
次のアニメーションは、入力式が上記の SLR(1) 文法によってどのように解析されるかを示しています。
質問の文法も LR(0) ではありません。
#S --> Aa | bAc | dc | bda
#A --> d
G = {}
NTs = ['S', 'A']
Ts = {'a', 'b', 'c', 'd'}
G['S'] = [['A', 'a'], ['b', 'A', 'c'], ['d', 'c'], ['b', 'd', 'a']]
G['A'] = [['d']]
次の LR0 DFA と解析テーブルからわかるように:
shift / reduce の競合が再び発生しています。
ただし、フォームの文字列を受け入れる次の文法a^ncb^n, n >= 1は LR(0) です。
あ → あ あ b
あ→あ
し→あ
# S --> A
# A --> a A b | c
G = {}
NTs = ['S', 'A']
Ts = {'a', 'b', 'c'}
G['S'] = [['A']]
G['A'] = [['a', 'A', 'b'], ['c']]
次の図からわかるように、生成された解析テーブルには競合がありません。
a^2cb^2次のコードを使用して、上記の LR(0) 解析テーブルを使用して入力文字列を解析する方法を次に示します。
def parse(input, parse_table, rules):
input = 'aaacbbb$'
stack = [0]
df = pd.DataFrame(columns=['stack', 'input', 'action'])
i, accepted = 0, False
while i < len(input):
state = stack[-1]
char = input[i]
action = parse_table.loc[parse_table.states == state, char].values[0]
if action[0] == 's': # shift
stack.append(char)
stack.append(int(action[-1]))
i += 1
elif action[0] == 'r': # reduce
r = rules[int(action[-1])]
l, r = r['l'], r['r']
char = ''
for j in range(2*len(r)):
s = stack.pop()
if type(s) != int:
char = s + char
if char == r:
goto = parse_table.loc[parse_table.states == stack[-1], l].values[0]
stack.append(l)
stack.append(int(goto[-1]))
elif action == 'acc': # accept
accepted = True
df2 = {'stack': ''.join(map(str, stack)), 'input': input[i:], 'action': action}
df = df.append(df2, ignore_index = True)
if accepted:
break
return df
parse(input, parse_table, rules)
次のアニメーションはa^2cb^2、上記のコードを使用して入力文字列が LR(0) パーサーで解析される方法を示しています。
