一个编译器的前端通常包括词法分析器和语法分析器。在分析过程中，文本输入词法分析器，根据词法规则解析出词法单元。词法单元作为输入，进入到语法分析器。语法分析器根据语法规则对词法单元序列进行分析（自顶而下，自底向上），确认词法单元序列符合语言的语法规则。在分析的同时形成翻译方案，由源语言（输入文本的语言）转换成目标语言（通常是一种中间语言）的过程。
这篇文章是《编译原理》（龙书）第二版第五章练习5.5的一个作业。
将 if (C) S1 else S2 实现为一个语法分析器。
这个作业基本涵盖了编译器前端的最主要的技术，又很好的简化了词法和语法种类带来的复杂性。因此值得作为对编译技术的研究案例。
本文逐步回顾编译器前端的关键技术，并在过程中用python实现。这个句型是C语言的，翻译的目标语言是一种接近汇编语言模式的伪代码。
词法分析器
词法分析器的主要作用是从文本中分析并提取语素(lexeme)并生成词法单元(token)。提供给语法分析器作为语法分析的基本单位。
词法分析器一般以正则模式作为区分，来识别不同的词法单元。
需要识别的词法
在这里，词法分析器需要识别的模式有：
- 空白字符
包括空格，制表符\t, 和换行\n。将文本分隔为不同的单元，它们在词法分析过程的第一步被剔除，不进入语法分析，我们在这里以空格为基本模式。 - 分隔符
分隔符一般指语法中有语法作用的标点符号，它本身是一个词法单元，它还将连在一起的字符分开成不同的词法单元。这里指( ) - 关键字
if 和 else
在这个语句中，C，S1 和 S2实际上是一个文法单元的非终结符号(None terminal)，分别是Condition(条件表达式)和Statement(语句)。
关于表达式的定义不在此赘述。一般可以求值的，或者说可以赋值给一个变量的就作为一个表达式(x = expr)。语句主要产生副作用。为求简便，我们在这里先将其实现为一个词法值，当词法器识别 'C' ，就认为它是一个语法单元的条件表达式。'S1', 'S2' 分别作为两个不同的语句。我们将在实现的过程中根据需要来决定是否扩展它。在编译过程中，C，S1，S2作为语法单元，实际上是由语法分析器在语法分析的过程中展开或者规约得到的语法树的节点，正常词法分析器输出的全部是终结符号，在这里暂时替代一下，这一点要注意不要混淆。
因此， 我们需要识别的词法有：
- 空格
- 分隔符( )，返回一个delimiter类型的词法单元，值为它的字符。
- 关键字 if 和 else，分别返回一个keyword类型的词法单元，值为字符串本身。
- 暂时替换的语法符号（非终结符）C，S1，S2。返回一个非终结符，值为它的字符，我们会附加一些属性给这个符号。
词法分析器的作用
词法分析器的重要作用是识别正则模式，一般命名变量，或者识别数字，或者字符串时，都通过正则引擎来识别。在这里我们需要识别的模式比较简单，全部是确定字符。
正则引擎的实现原理是有限自动机(finite-automata)，有两种类型，NFA和DFA，非确定有限自动机和确定型有限自动机。可以根据算法机械构造NFA，然后再根据算法机械转换为DFA。
https://github.com/dannyvi/simple-regex 实现了一个简单的NFA的正则引擎。我们将用这个引擎来识别词法单元。它可以用正则模式生成一个有限自动机，并识别相应的字符串是否匹配这个模式。
python的re模块文档中给出了一个词法器更完整的例子。Writing a Tokenizer
下面是词法器代码：
from regex import regex_compile
space = regex_compile(r" ")
delimiter = regex_compile(r"\(|\)")
keyword = regex_compile(r"(if)|(else)")
node = regex_compile(r"(S1)|(S2)|C")
class Token:
def __init__(self, typ, value):
self.typ = typ
self.value = value
def __repr__(self):
return '<token: {}.{} >'.format(self.typ, self.value)
def tokenizer(input_stream):
def split(input_stream):
symbol = ''
for i in input_stream:
if space.match(i):
if symbol:
yield symbol
symbol = ''
elif delimiter.match(i):
if symbol:
yield symbol
symbol = ''
yield i
else:
symbol += i
if symbol:
yield symbol
def token(value):
if delimiter.match(value): return Token(value, value)
elif keyword.match(value): return Token(value, value)
elif node.match(value): return Token(value, value)
else: raise RuntimeError('"{}" unexpected symbol'.format(value))
l = split(input_stream)
return map(token, l)
这个词法器有两个pass，首先将代码用空白符和分隔符分开成为一个列表，然后对这个列表分析返回一个Token的map迭代对象。
from tokenizer import tokenizer
s = tokenizer("if ( C ) S1 else S2 ")
list(s)
Out[4]:
[<token: if.if >,
<token: (.( >,
<token: C.C >,
<token: ).) >,
<token: S1.S1 >,
<token: else.else >,
<token: S2.S2 >]
语法分析和翻译
一个语法分析器主要的作用是按照给定的文法将词法单元序列规约为语法树，并将这个语法树翻译为目标语言。一般在规约时就可以展开翻译，所以语法分析和翻译同时进行。
标准 LR(1)分析器 (Canonical LR(1))
其他的分析器还有LL(1)，SLR(LR 0)，LALR(LR 1)。不过我们在这里就实现 Canonical LR(1)。
LR分析器是通过移入规约技术来实现分析过程的，所以分成两个阶段，首先构建语法分析表，然后按分析表进行规约和翻译。
实际上语法分析相当于构建一个有限状态机，由开始符号进入，并对不同的输入进行状态转化，当输入完成后，如果状态处于接受状态，就表示分析成功了。
语法分析表
通过算法将上下文无关文法G转化为语法分析动作。我们可以先将其转化为一个分析表，然后再对照分析表，来编写分析和翻译动作。
分析表形状大概如下：
ACTION
| 状态\输入 | a | b | c |
|---|---|---|---|
| 0 | s2 | e1 | s1 |
| 1 | r2 | r1 | acc |
| 2 | e3 | s1 | s2 |
GOTO
| 状态\非终结符 | S | N |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
ACTION 负责对输入的终结符号选择合适的动作（移入，规约，报错，接受）， GOTO负责对规约后的产生式进行状态转化。
语法分析在一个分析状态栈（或者分析状态序列）上操作。如果文本属于这个语法的话，移入的状态最终会被规约为开始符号。
语法分析表G算法如下：
输入： 文法G
输出：分析表
方法：
构造G的LR(1)项集族C={I0, I1,...In}。
语法分析器的状态i由Ii构造得到，状态i按照下面规则构建：
- 如果[A -> α∙aβ, b]，并且GOTO(Ii, a) = ij, 那么将ACTION[i, a]设置为移入j("sj")。a必须是终结符。
- 如果[A -> α∙, a] 在 Ii中，且A不是开始符号，那么将ACTION[i, a]设置为规约 A -> α ( "rn"，n是产生式的编号 )。
- 如果[S' -> S, $] 在Ii中，那么将ACTION[i, $]设置为接受("acc")。
状态i对于各个非终结符号A的goto按照下面规则构造：
如果GOTO(Ii, A) = Ij, 那么 GOTO[i, A] = j所有没按照2, 3条规则定义的分析表条目都设置为错误。
语法分析表的初始状态是由 [S' -> ∙S, $] 的项集构造得到的状态。
所以，项集族，状态和输入符号决定了这个表的构造。
输入符号就是文法里面的终结符号(Terminal)和非终结符号(None Terminal)。
状态就简单理解为项集族里面的项集闭包(Item-sets Closure)的编号。
项集族(Item-sets Closure Collections)
项集族是由项集闭包组成的，它是构造出来的一个文法的状态机的全部状态。
项集闭包(Item-sets Closure)
一个项集闭包就是一个状态，大概解释就是在这个状态上进行输入转换可能用到的全部产生式组成的项。
项(Item)
标准 LR(1)分析器的项是由产生式，当前位置和输入字符构成的。
class Item(object):
"""The Canonical LR(1) Item definition.
:param symbol: str, the left part of production.
:param body: str, the right part of production.
:param dot: int, current position in the item.
:param follow: str, possible input for the current configuration.
"""
def __init__(self, symbol, body, dot, follow):
self.symbol = symbol
self.body = body
self.pos = dot
self.follow = follow
def __str__(self):
p = list(self.body)
p.insert(self.pos, '◆')
pr = ' '.join(p)
return "[{}] {} -> {}".format( self.follow, self.symbol, pr)
def __repr__(self):
return "<Item:{} >\n".format(self.__str__())
def __eq__(self, other):
if isinstance(other, Item):
return ((self.symbol == other.symbol) and
(self.body == other.body) and
(self.pos == other.pos) and
(self.follow == other.follow))
else:
return False
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
return hash(self.__str__())
实现了项，和相关的操作。因为它在闭包中作为集合元素，所以实现 __hash__ ， __eq__ 和 __ne__ 方法，这样集合就可以迭代。
from regex.parsing_table import Item
i1 = Item('S', 'b|c', 2, 'k')
i1
Out[4]: <Item: S -> b|.c k >
项集闭包的实现
class定义：
class Closure(object):
def __init__(self, sets: Set[Item], label: int = None):
self.label = label
self.sets = sets
self.goto = dict() # type: dict[str, int]
def __len__(self):
return len(self.sets)
def __iter__(self):
return self.sets.__iter__()
def __str__(self):
return "\n".join([i.__str__() for i in self.sets])
def __repr__(self):
return "<Closure>:{}\n{}\n</Closure>\n".format(self.label,
self.__str__())
def __eq__(self, other):
return self.sets == other.sets
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
return hash(self.__str__())
def __contains__(self, item):
return item in self.sets
sets包含所有的项，label是这个闭包的状态名，这里规定为一个数字，goto是一个字典，用于记录这个状态在不同输入的转换目标状态。
__contains__ 用于计算项(Item)是否包含在这个闭包中。
因为闭包还会包含在族(collection)中作为一个元素，所以也实现 __eq__ 和 __hash__，这样集合就可以作为一个迭代器 。
项集闭包的算法：
对于一个项集(Item-sets) I ，计算它的闭包 CLOSURE(I) 。
- 将 I 中的各个项加入到闭包当中。
- 闭包中的每个项， 如 [A -> α∙Bβ, a]，对文法G中的每个非终结符B的产生式 B -> γ，对FIRST(βa)中的每个终结符 b, 将 [B -> ∙γ, b] 加入闭包当中。
这里的∙B是推理当前位置后面可能出现的规约（B的产生式），以及B规约结束之后，能够在之后出现的终结符。
def get_closure(cl: Closure, label: int) -> Closure:
"""get all Item of a Closure from given Items, by adding implied Items.
The implied Items are the productions of the None terminals after the
current position, which put a dot on the head."""
def get_nterm(item):
pos, prod = (item.pos, item.body)
if pos < len(prod):
symbol = prod[pos]
if isnterm(symbol):
return symbol
return None
item_set = set()
q = queue.Queue()
for i in cl.sets:
item_set.add(i)
q.put(i)
while not q.empty():
item = q.get()
symbol = get_nterm(item)
if symbol:
products = [i for i in grammar if i[0] == symbol]
suffix = item.body[item.pos+1:] + item.follow
termins = firsts(suffix)
for product in products:
for terminal in termins:
new_item = Item(symbol, product[1], 0, terminal)
if new_item not in item_set:
item_set.add(new_item)
q.put(new_item)
c = Closure(item_set, label)
return c
我们需要知道关于grammar和firsts的定义。
grammar = [ ("stmt", ("if", "(", "C", ")", "S", "else", "S")),
...
]
grammar 在这里定义为一个产生式列表。产生式是由一个头部和体合成的元组，产生式的体本身也是一个元组。
firsts是为了计算一个产生式的体中可能出现的第一个终结符号，我们在规约时需要知道可能出现的下一个终结符号和应该使用哪一个式子来进行规约。这样我们在推导的时候就能知道应该进入的状态。
对于一个终结符号或者非终结符号， 它的first(X)算法如下：
- X是终结符号: first(X) = X
- X是非终结符号：查找产生式 X -> Y1Y2...Yk, 如果Y1是非终结符且含有空产生式，那么 first(X) = first(Y1) ∪ firsts(Y2...Yk), 否则就等于 first(Y1),意思就是空产生式会形成多种可能性，确定只有一个first的符号，后面的符号就排除掉了。如果Y是终结符号，就不用下推。如果Y是非终结符号，就考虑它是否产生空产生式，来决定考察下一个符号。
- X是EPSILON: firsts(X) += EPSILON
具体的实现是这样的：
def isnterm(symbol):
return symbol in n_terminals
def isterm(symbol):
return symbol in terminals
def produce_epsilon(none_terminal):
return 'EPSILON' in [i[1] for i in grammar if i[0] == none_terminal]
# def is_start_symbol(symbol):
# return symbol == "startsup"
def first(symbol):
"""Return the first terminal sets that may occur in the Symbol."""
first_sets = set()
if isterm(symbol):
return set(symbol)
elif produce_epsilon(symbol):
first_sets = first_sets.union('EPSILON')
elif isnterm(symbol):
for i in grammar:
if i[0] == symbol:
body = i[1]
epsilons = True
current = 0
while epsilons is True and current < len(body):
if body[current] != symbol:
first_sets = first_sets.union(first(body[current]))
if not produce_epsilon(body[current]):
epsilons = False
current += 1
return first_sets
def firsts(suffix):
if len(suffix) == 1:
return first(suffix[0])
else:
if not produce_epsilon(suffix[0]):
return first(suffix[0])
else:
return first(suffix[0]).union(firsts(suffix[1:]))
isnterm, isterm 分别判断是否终结符号。
produce_epsilon 产生式的特殊形式，判断是否一个空产生式。这里约定空产生式 N -> EPSILON 的体由 EPSILON 定义。
is_start_symbol 判断是否开始符号。
first 计算一个终结符号或者非终结符号可能出现的第一个终结符。
firsts 计算一个句型（多个符号连在一起）可能出现的第一个终结符。
为求简单我们在这里将 grammar, terminals, n_terminals 定义为列表。以后再实现如何将文法规则解析为python对象，和判断是否终结符号的算法。
grammar = [("startsup", ("start")),
("start", ("stmt")),
("stmt", ("if", "(", "C", ")", "S1", "else", "S2")),
]
terminals = ("if", "(", "C", ")", "S", "else", "S2", "$")
n_terminals = ("startsup", "start", "stmt")
实际上 C, S1, S2 都应该是非终结符号。未来会替换为产生式，由编译器规约它们的体来得到节点。
这个文法是对原文法进行增广后的增广文法，由原来的产生式
- start -> stmt
- stmt -> if ( c ) S1 else S2
增加一个开始符号start'和在尾部增加一个结束输入$ , 对原来的词法序列在尾部增加一个终结字符 $, 这样当扫描到最后一个字符为 $, 就进入接受状态。
- startsup -> start
这样我们就实现了项集闭包的算法。
推导项集族
项集族C的算法：
- 在C中，初始添加 [startsup -> ◆ start, $] 的项 【由Item('startsup', ('start',), 0, '$')构造】，并计算闭包【get_closure(item)】为开始状态。
- 在C中，对于每一个项集闭包I， 对于每一个文法符号X，可以是终结符号或者非终结符号，如果 goto(I, X) 非空且不在C中， 就加入到C中。
通过将每一个输入可能得到的状态加入到项集族，来完成构建。
这里，goto(I,X)指的是状态 I 在输入X下转换到的状态。(一个项集闭包）它的算法：
I中所有存在的项 [A -> α∙Xβ, a], 将 [A -> αX∙β, a]加入到集合，并计算它的闭包。
实现如下：
def goto(clos: Closure, letter: str) -> Closure:
"""a closure that could get from the current closure by input a letter.
:param clos: the current closure.
:param letter: the input letter.
:return: Closure.
"""
item_set = set()
for item in clos.sets:
dot, prod = (item.pos, item.body)
if dot < len(prod) and prod[dot] == letter:
new_item = Item(item.symbol,
item.body,
item.pos + 1,
item.follow)
item_set.add(new_item)
c = Closure(item_set)
return get_closure(c, label=None)
def closure_groups():
def find_label(closure, group):
for i in group:
if closure == i:
return i.label
return None
group = set()
all_symbols = terminals + n_terminals
label = 0
start_item = Item('startsup', 'start', 0, '$')
start = get_closure(Closure({start_item}), label)
q = queue.Queue()
q.put(start)
group.add(start)
while not q.empty():
c = q.get()
for literal in all_symbols: # terminals + n_terminals:
go_clos = goto(c, literal)
if go_clos:
if go_clos not in group:
label += 1
go_clos.label = label
group.add(go_clos)
q.put(go_clos)
c.goto[literal] = label
else:
go_label = find_label(go_clos, group)
if go_label:
c.goto[literal] = go_label
return group
得到了整个文法的项集族之后，我们就可以根据之前给出的构建出语法分析表了。这里将终结符号的ACTION和非终结符号的GOTO拼接在一起。并且没有🙅♂️错误处理，这里默认将错误动作全部初始化为'.'。
def get_states_map(closure_group):
def get_state_map(closure):
""" table row like all_symbols list state maps."""
all_symbols = terminals + n_terminals
row = ["." for i in all_symbols]
# None terminals GOTO action and Terminals shift action.
for input, goto_label in closure.goto.items():
row_pos = all_symbols.index(input)
for item in closure:
if item.pos < len(item.body): # shape like [A -> ⍺.aβ b]
if item.body[item.pos] == input:
# None terminals GOTO state
if input in n_terminals:
row[row_pos] = str(goto_label)
# Terminals action shift state
elif input in terminals:
row[row_pos] = "s" + str(goto_label)
# Terminals reduce action. shape like [A -> ⍺. a]
for row_pos, input in enumerate(all_symbols):
for item in closure:
if item.pos == len(item.body) and \
item.follow == input and \
item.symbol != 'startsup':
# 'R' should be replaced with start_symbol
#if item.follow != '*':
production_num = grammar.index([item.symbol, item.body])
row[row_pos] = 'r' + str(production_num)
#else:
# pass
# accept condition 'startsup -> start. , $'
acc_item = Item('startsup', 'start', 1, '$')
if acc_item in closure:
input = '$'
row_pos = all_symbols.index('$')
row[row_pos] = '$'
return row
state_map = [None for i in range(len(closure_group))]
for closure in closure_group:
row = get_state_map(closure)
state_map[closure.label] = row
return state_map
def generate_syntax_table():
g = closure_groups()
state_map = get_states_map(g)
return state_map
这样就得到了语法分析表。
全部代码在这里：
import queue
from typing import Set
grammar = [("startsup", ("start", )),
("start", ("stmt", )),
("stmt", ("if", "(", "C", ")", "S1", "else", "S2")),
]
terminals = ("if", "(", "C", ")", "S1", "else", "S2", '$')
n_terminals = ("startsup", "start", "stmt")
all_symbols = terminals + n_terminals
class Item(object):
"""The Canonical LR(1) Item definition.
:param symbol: str, the left part of production.
:param body: str, the right part of production.
:param dot: int, current position in the item.
:param follow: str, possible input for the current configuration.
"""
def __init__(self, symbol, body, dot, follow):
self.symbol = symbol
self.body = body
self.pos = dot
self.follow = follow
def __str__(self):
p = list(self.body)
p.insert(self.pos, '◆')
pr = ' '.join(p)
return "[{}] {} -> {}".format( self.follow, self.symbol, pr)
def __repr__(self):
return "<Item:{} >\n".format(self.__str__())
def __eq__(self, other):
if isinstance(other, Item):
return ((self.symbol == other.symbol) and
(self.body == other.body) and
(self.pos == other.pos) and
(self.follow == other.follow))
else:
return False
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
return hash(self.__str__())
class Closure(object):
def __init__(self, sets: Set[Item], label: int = None):
self.label = label
self.sets = sets
self.goto = dict() # type: dict[str, int]
def __len__(self):
return len(self.sets)
def __iter__(self):
return self.sets.__iter__()
def __str__(self):
return "\n".join([i.__str__() for i in self.sets])
def __repr__(self):
return "<Closure>:{}\n{}\n</Closure>\n".format(self.label,
self.__str__())
def __eq__(self, other):
return self.sets == other.sets
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
return hash(self.__str__())
def __contains__(self, item):
return item in self.sets
def isnterm(symbol):
return symbol in n_terminals
def isterm(symbol):
return symbol in terminals
def produce_epsilon(none_terminal):
return 'EPSILON' in [i[1] for i in grammar if i[0] == none_terminal]
def first(symbol):
"""Return the first terminal sets that may occur in the Symbol."""
first_sets = set()
if isterm(symbol):
return set(symbol)
elif produce_epsilon(symbol):
first_sets = first_sets.union('EPSILON')
elif isnterm(symbol):
for i in grammar:
if i[0] == symbol:
body = i[1]
epsilons = True
current = 0
while epsilons is True and current < len(body):
if body[current] != symbol:
first_sets = first_sets.union(first(body[current]))
if not produce_epsilon(body[current]):
epsilons = False
current += 1
return first_sets
def firsts(suffix):
if len(suffix) == 1:
return first(suffix[0])
else:
if not produce_epsilon(suffix[0]):
return first(suffix[0])
else:
return first(suffix[0]).union(firsts(suffix[1:]))
def get_closure(cl: Closure, label: int) -> Closure:
"""get all Item of a Closure from given Items, by adding implied Items.
The implied Items are the productions of the None terminals after the
current position, which put a dot on the head."""
def get_nterm(item):
pos, prod = (item.pos, item.body)
if pos < len(prod):
symbol = prod[pos]
if isnterm(symbol):
return symbol
return None
item_set = set()
q = queue.Queue()
for i in cl.sets:
item_set.add(i)
q.put(i)
while not q.empty():
item = q.get()
symbol = get_nterm(item)
if symbol:
products = [i for i in grammar if i[0] == symbol]
suffix = item.body[item.pos+1:] + tuple(item.follow)
termins = firsts(suffix)
for product in products:
for terminal in termins:
new_item = Item(symbol, product[1], 0, terminal)
if new_item not in item_set:
item_set.add(new_item)
q.put(new_item)
c = Closure(item_set, label)
return c
def goto(clos: Closure, letter: str) -> Closure:
"""a closure that could get from the current closure by input a letter.
:param clos: the current closure.
:param letter: the input letter.
:return: Closure.
"""
item_set = set()
for item in clos.sets:
dot, prod = (item.pos, item.body)
if dot < len(prod) and prod[dot] == letter:
new_item = Item(item.symbol,
item.body,
item.pos + 1,
item.follow)
item_set.add(new_item)
c = Closure(item_set)
return get_closure(c, label=None)
def closure_groups():
def find_label(closure, group):
for i in group:
if closure == i:
return i.label
return None
group = set()
label = 0
start_item = Item('startsup', ('start',), 0, '$')
start = get_closure(Closure({start_item}), label)
q = queue.Queue()
q.put(start)
group.add(start)
while not q.empty():
c = q.get()
for literal in all_symbols: # terminals + n_terminals:
go_clos = goto(c, literal)
if go_clos:
if go_clos not in group:
label += 1
go_clos.label = label
q.put(go_clos)
group.add(go_clos)
c.goto[literal] = label
# print('add closure', go_clos)
else:
go_label = find_label(go_clos, group)
if go_label:
c.goto[literal] = go_label
return group
def get_states_map(closure_group):
def get_state_map(closure):
""" table row like all_symbols list state maps."""
row = ["." for i in all_symbols]
# None terminals GOTO action and Terminals shift action.
for input, goto_label in closure.goto.items():
row_pos = all_symbols.index(input)
for item in closure:
if item.pos < len(item.body): # shape like [A -> ⍺.aβ b]
if item.body[item.pos] == input:
# None terminals GOTO state
if input in n_terminals:
row[row_pos] = str(goto_label)
# Terminals action shift state
elif input in terminals:
row[row_pos] = "s" + str(goto_label)
# Terminals reduce action. shape like [A -> ⍺. a]
for row_pos, input in enumerate(all_symbols):
for item in closure:
if item.pos == len(item.body) and \
item.follow == input and \
item.symbol != 'startsup':
# 'R' should be replaced with start_symbol
#if item.follow != '*':
production_num = grammar.index((item.symbol, item.body))
row[row_pos] = 'r' + str(production_num)
#else:
# pass
# accept condition 'startsup -> start. , $'
acc_item = Item('startsup', ('start',), 1, '$')
if acc_item in closure:
input = '$'
row_pos = all_symbols.index('$')
row[row_pos] = '$'
return row
state_map = [None for i in range(len(closure_group))]
for closure in closure_group:
row = get_state_map(closure)
state_map[closure.label] = row
return state_map
def generate_syntax_table():
g = closure_groups()
state_map = get_states_map(g)
return state_map
看下结果：
from parser import *
n = generate_syntax_table()
n
state if ( C ) S1 else S2 $ startsup start stmt
0 s1 . . . . . . . . 2 3
1 . s4 . . . . . . . . .
2 . . . . . . . $ . . .
3 . . . . . . . r1 . . .
4 . . s5 . . . . . . . .
5 . . . s6 . . . . . . .
6 . . . . s7 . . . . . .
7 . . . . . s8 . . . . .
8 . . . . . . s9 . . . .
9 . . . . . . . r2 . . .
语法分析和翻译
语法分析
语法分析器在一个状态栈上工作，这个栈存储了移入的状态，它代表了已经输入，尚未规约的词法单元。语法分析器对token_stream(经过词法器解析后的代码)的词法单元逐个进行4种操作。分析器在分析开始前移入状态0。分析器以状态栈上的最后一个状态（栈顶）为当前状态，并且根据输入字符查分析表，来获得当前操作。
四种分析操作：
移入，将目标状态移入到状态栈顶。进入下一个词法单元。
规约，规约目标产生式，当前词法单元不变，继续查表进行下一个操作，直到当前词法单状态元被移入。
接受，在含有增广文法开始符号产生式的项 [startsup -> start◆, '$']，如果当前输入为 '$'， 分析成功进入接受状态，并结束。
错误， 目前我们忽略错误处理。
代码如下：
class SDT:
def __init__(self):
self.syntax_table = generate_syntax_table()
self.state_stack = [0]
self.accept = False
def get_action(self, state, literal):
return self.syntax_table[state][all_symbols.index(literal)]
def ahead(self, token):
action = self.get_action(self.state_stack[-1], token.typ)
# shift action push a current state into state_stack
if action[0] == 's':
current_state = int(action[1:])
self.state_stack.append(current_state)
elif action[0] == '$':
self.accept = True # success
# reduce action reduct a production and push
elif action[0] == 'r':
# get the production in grammar
number = int(action[1:])
production = grammar[number]
head, body = production
# pop the states of production body
for _ in body:
self.state_stack.pop()
# push the state of head GOTO(I,X)
state = self.get_action(self.state_stack[-1], head)
self.state_stack.append(int(state))
# reduce actions does not consume a token,
# only when shifting, a token was consume and passed
self.ahead(token)
else:
raise SyntaxError(f"Not a correct token '{token.__str__()}'.")
def parse(self, token_stream):
while True:
try:
token = next(token_stream)
self.ahead(token)
except StopIteration:
# patch "$" in the end of token stream
# to match the augmented grammar
self.ahead(Token("$", "$"))
break
它接受一个词法单元流，并且分析，如果分析成功，accept就设置为True
from tokenizer import tokenizer
token_stream = tokenizer("if (C) S1 else S2")
sdt = SDT()
sdt.parse(token_stream)
sdt.accept
Out[8]: True
翻译方案
翻译方案一般插入到分析过程当中。
每个非终结符号都会形成一个函数，我们这里暂时在代码中预定义好非终结符号的翻译函数。
因为LR分析器是从右到左规约，而在移入的时候并不判断目前在哪个产生式的内部，因此翻译方案用后缀翻译来实现，就是在规约的时候翻译。产生式头部的名称作为函数名，规约的内容作为参数来进行调用，向上返回函数的结果。
建立一个参数栈:
self.arg_stack = []
token在移入的时候作为值移入到栈中。
self.push_arg(token)
规约时，将值移出，作为规约函数的参数。返回的结果，就是非终结符号的值，移入到栈中。
# translations
args = []
for _ in body:
arg = self.arg_stack.pop()
args.insert(0, arg)
translation = globals().get(head).__call__(*args)
self.arg_stack.append(translation)
然而后缀翻译方案只适用于综合属性（S属性），对于继承属性并不适用。比如 stmt -> if (C) S1 else S2 大致会形成如下翻译方案:
C.code
S1.scode
goto stmt.next
label L1
S2.code
其中，stmt.next 由外部传入，是stmt作为产生式的体时的继承属性，LL分析器通过预测分析表已经获取了头部，所以可以预先分配一个值。这里由于分析器是规约方式的，因此尚不知道继承属性的值。一般采取用一个空产生式来替代翻译内容并先生成继承属性的方法来解决，不过会带来语法分析时的复杂性。
我们在这里采用延迟调用的方法，就是 stmt 规约完成后并不直接返回翻译的字符串值（因为还有一些属性不知道）， 而是返回一个函数，通过将未知的内容包装成参数向上返回，在进行规约 start -> stmt 时， 再将start 生成的必要值作为参数来调用 stmt 规约的返回值，就可以获得正确的翻译方案了。
def stmt(IF, LPAR, c, RPAR, s1, ELSE, s2):
def call(next_label):
L1 = get_label()
C_code = c.code(f_cond=L1)
S1_code = s1.code()
S2_code = s2.code()
inter_code = """
{}
{}
goto {}
label {}
{}""".format(C_code, S1_code, next_label, L1, S2_code)
return inter_code
return call
添加对结束状态的处理，和一些其他必要动作。这样，分析和翻译方案就变成了：
class SDT:
def __init__(self):
self.syntax_table = generate_syntax_table()
self.state_stack = [0]
self.arg_stack = []
self.accept = False
self.translation = ''
def get_action(self, state, literal):
return self.syntax_table[state][all_symbols.index(literal)]
def ahead(self, token):
action = self.get_action(self.state_stack[-1], token.typ)
# shift action push a current state into state_stack
if action[0] == 's':
current_state = int(action[1:])
self.state_stack.append(current_state)
self.push_arg(token)
elif action[0] == '$':
self.translation = startsup(self.arg_stack[-1])
self.accept = True # success
print('SUCCESS')
print(self.translation)
# reduce action reduct a production and push
elif action[0] == 'r':
# get the production in grammar
number = int(action[1:])
production = grammar[number]
head, body = production
# pop the states of production body
for _ in body:
self.state_stack.pop()
# push the state of head GOTO(I,X)
state = self.get_action(self.state_stack[-1], head)
self.state_stack.append(int(state))
# translations
args = []
for _ in body:
arg = self.arg_stack.pop()
args.insert(0, arg)
translation = globals().get(head).__call__(*args)
self.arg_stack.append(translation)
# reduce actions does not consume a token,
# only when shifting, a token was consume and passed
self.ahead(token)
else:
raise SyntaxError(f"Not a correct token '{token.__str__()}'.")
def parse(self, token_stream):
while True:
try:
token = next(token_stream)
self.ahead(token)
except StopIteration:
# patch "$" in the end of token stream
# to match the augmented grammar
self.ahead(Token("$", "$"))
break
def push_arg(self, token):
if token.typ == 'C':
token.code = lambda f_cond: 'Ccode Cfalse = {}'.format(f_cond)
elif token.typ == 'S1':
token.code = lambda : 'S1code'
elif token.typ == 'S2':
token.code = lambda : 'S2code'
self.arg_stack.append(token)
all_labels = []
def get_label():
n = 'L' + str(len(all_labels))
all_labels.append(n)
return n
def stmt(IF, LPAR, c, RPAR, s1, ELSE, s2):
def call(next_label):
L1 = get_label()
C_code = c.code(f_cond=L1)
S1_code = s1.code()
S2_code = s2.code()
inter_code = """
{}
{}
goto {}
label {}
{}""".format(C_code, S1_code, next_label, L1, S2_code)
return inter_code
return call
def start(stmt):
def call():
L = get_label()
return stmt(L)
return call
def startsup(f):
return f()
运行一下，
from parser import SDT
from tokenizer import tokenizer
token_stream = tokenizer('if (C) S1 else S2')
sdt = SDT()
sdt.parse(token_stream)
成功翻译：
Ccode Cfalse = L1
S1code
goto L0
label L1
S2code
这是个简陋的过程，但是核心功能完整，我们可以在之后的过程中，逐步完善它。
通常，词法规则和语法规则是由单独的文件定义的。所以需要对词法规则和语法规则进行解析的构件，来完成从源文本到python对象的转换。翻译方案通常嵌入到语法规则中。
错误处理可以在适当的情况引入到编译过程当中。
另外，二义性文法，空产生式等情况的转换在语法添加的过程当中会浮现。
当然还有为语法规则添加基本的语句，使之逐渐成为一个完善的编译前端。
不论如何，我们已经完成了编译前端从源语言到目标语言的全部流程，是一个成功的开始。
