一個(gè)編譯器的前端通常包括詞法分析器和語(yǔ)法分析器陌僵。在分析過(guò)程中钞艇，文本輸入詞法分析器，根據(jù)詞法規(guī)則解析出詞法單元窍箍。詞法單元作為輸入，進(jìn)入到語(yǔ)法分析器丽旅。語(yǔ)法分析器根據(jù)語(yǔ)法規(guī)則對(duì)詞法單元序列進(jìn)行分析（自頂而下椰棘，自底向上），確認(rèn)詞法單元序列符合語(yǔ)言的語(yǔ)法規(guī)則榄笙。在分析的同時(shí)形成翻譯方案邪狞，由源語(yǔ)言（輸入文本的語(yǔ)言）轉(zhuǎn)換成目標(biāo)語(yǔ)言（通常是一種中間語(yǔ)言）的過(guò)程。

這篇文章是《編譯原理》（龍書(shū)）第二版第五章練習(xí)5.5的一個(gè)作業(yè)茅撞。

將 if (C) S1 else S2 實(shí)現(xiàn)為一個(gè)語(yǔ)法分析器帆卓。

這個(gè)作業(yè)基本涵蓋了編譯器前端的最主要的技術(shù)，又很好的簡(jiǎn)化了詞法和語(yǔ)法種類(lèi)帶來(lái)的復(fù)雜性米丘。因此值得作為對(duì)編譯技術(shù)的研究案例剑令。

本文逐步回顧編譯器前端的關(guān)鍵技術(shù)，并在過(guò)程中用python實(shí)現(xiàn)拄查。這個(gè)句型是C語(yǔ)言的吁津，翻譯的目標(biāo)語(yǔ)言是一種接近匯編語(yǔ)言模式的偽代碼。

詞法分析器

詞法分析器的主要作用是從文本中分析并提取語(yǔ)素(lexeme)并生成詞法單元(token)堕扶。提供給語(yǔ)法分析器作為語(yǔ)法分析的基本單位碍脏。

詞法分析器一般以正則模式作為區(qū)分，來(lái)識(shí)別不同的詞法單元稍算。

需要識(shí)別的詞法

在這里典尾，詞法分析器需要識(shí)別的模式有：

• 空白字符
  包括空格，制表符\t, 和換行\(zhòng)n糊探。將文本分隔為不同的單元钾埂，它們?cè)谠~法分析過(guò)程的第一步被剔除，不進(jìn)入語(yǔ)法分析科平，我們?cè)谶@里以空格為基本模式勃教。
• 分隔符
  分隔符一般指語(yǔ)法中有語(yǔ)法作用的標(biāo)點(diǎn)符號(hào)，它本身是一個(gè)詞法單元匠抗，它還將連在一起的字符分開(kāi)成不同的詞法單元故源。這里指( )
• 關(guān)鍵字
  if 和 else

在這個(gè)語(yǔ)句中，C汞贸，S1 和 S2實(shí)際上是一個(gè)文法單元的非終結(jié)符號(hào)(None terminal)绳军，分別是Condition(條件表達(dá)式)和Statement(語(yǔ)句)印机。
關(guān)于表達(dá)式的定義不在此贅述。一般可以求值的门驾，或者說(shuō)可以賦值給一個(gè)變量的就作為一個(gè)表達(dá)式(x = expr)射赛。語(yǔ)句主要產(chǎn)生副作用。為求簡(jiǎn)便奶是，我們?cè)谶@里先將其實(shí)現(xiàn)為一個(gè)詞法值楣责，當(dāng)詞法器識(shí)別 'C' ，就認(rèn)為它是一個(gè)語(yǔ)法單元的條件表達(dá)式聂沙。'S1', 'S2' 分別作為兩個(gè)不同的語(yǔ)句秆麸。我們將在實(shí)現(xiàn)的過(guò)程中根據(jù)需要來(lái)決定是否擴(kuò)展它。在編譯過(guò)程中及汉，C沮趣，S1，S2作為語(yǔ)法單元坷随，實(shí)際上是由語(yǔ)法分析器在語(yǔ)法分析的過(guò)程中展開(kāi)或者規(guī)約得到的語(yǔ)法樹(shù)的節(jié)點(diǎn)房铭，正常詞法分析器輸出的全部是終結(jié)符號(hào)，在這里暫時(shí)替代一下温眉，這一點(diǎn)要注意不要混淆缸匪。

因此， 我們需要識(shí)別的詞法有：

1. 空格
2. 分隔符( )类溢，返回一個(gè)delimiter類(lèi)型的詞法單元豪嗽，值為它的字符。
3. 關(guān)鍵字 if 和 else豌骏，分別返回一個(gè)keyword類(lèi)型的詞法單元龟梦，值為字符串本身。
4. 暫時(shí)替換的語(yǔ)法符號(hào)（非終結(jié)符）C窃躲，S1计贰，S2。返回一個(gè)非終結(jié)符蒂窒，值為它的字符躁倒，我們會(huì)附加一些屬性給這個(gè)符號(hào)。

詞法分析器的作用

詞法分析器的重要作用是識(shí)別正則模式洒琢，一般命名變量秧秉，或者識(shí)別數(shù)字，或者字符串時(shí)衰抑，都通過(guò)正則引擎來(lái)識(shí)別象迎。在這里我們需要識(shí)別的模式比較簡(jiǎn)單，全部是確定字符。
正則引擎的實(shí)現(xiàn)原理是有限自動(dòng)機(jī)(finite-automata)砾淌，有兩種類(lèi)型啦撮，NFA和DFA，非確定有限自動(dòng)機(jī)和確定型有限自動(dòng)機(jī)汪厨≡叽海可以根據(jù)算法機(jī)械構(gòu)造NFA，然后再根據(jù)算法機(jī)械轉(zhuǎn)換為DFA劫乱。
https://github.com/dannyvi/simple-regex 實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的NFA的正則引擎织中。我們將用這個(gè)引擎來(lái)識(shí)別詞法單元。它可以用正則模式生成一個(gè)有限自動(dòng)機(jī)衷戈，并識(shí)別相應(yīng)的字符串是否匹配這個(gè)模式狭吼。
python的re模塊文檔中給出了一個(gè)詞法器更完整的例子。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)

這個(gè)詞法器有兩個(gè)pass脱惰，首先將代碼用空白符和分隔符分開(kāi)成為一個(gè)列表，然后對(duì)這個(gè)列表分析返回一個(gè)Token的map迭代對(duì)象窿春。

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 >]

語(yǔ)法分析和翻譯

一個(gè)語(yǔ)法分析器主要的作用是按照給定的文法將詞法單元序列規(guī)約為語(yǔ)法樹(shù)拉一，并將這個(gè)語(yǔ)法樹(shù)翻譯為目標(biāo)語(yǔ)言。一般在規(guī)約時(shí)就可以展開(kāi)翻譯旧乞，所以語(yǔ)法分析和翻譯同時(shí)進(jìn)行蔚润。

標(biāo)準(zhǔn) LR(1)分析器 (Canonical LR(1))

其他的分析器還有LL(1)，SLR(LR 0)尺栖，LALR(LR 1)嫡纠。不過(guò)我們?cè)谶@里就實(shí)現(xiàn) Canonical LR(1)。

LR分析器是通過(guò)移入規(guī)約技術(shù)來(lái)實(shí)現(xiàn)分析過(guò)程的延赌，所以分成兩個(gè)階段除盏，首先構(gòu)建語(yǔ)法分析表，然后按分析表進(jìn)行規(guī)約和翻譯挫以。

實(shí)際上語(yǔ)法分析相當(dāng)于構(gòu)建一個(gè)有限狀態(tài)機(jī)者蠕，由開(kāi)始符號(hào)進(jìn)入，并對(duì)不同的輸入進(jìn)行狀態(tài)轉(zhuǎn)化掐松，當(dāng)輸入完成后踱侣，如果狀態(tài)處于接受狀態(tài)，就表示分析成功了大磺。

語(yǔ)法分析表

通過(guò)算法將上下文無(wú)關(guān)文法G轉(zhuǎn)化為語(yǔ)法分析動(dòng)作抡句。我們可以先將其轉(zhuǎn)化為一個(gè)分析表，然后再對(duì)照分析表杠愧，來(lái)編寫(xiě)分析和翻譯動(dòng)作待榔。

分析表形狀大概如下：

ACTION

GOTO

ACTION 負(fù)責(zé)對(duì)輸入的終結(jié)符號(hào)選擇合適的動(dòng)作（移入，規(guī)約流济，報(bào)錯(cuò)究抓，接受）猾担， GOTO負(fù)責(zé)對(duì)規(guī)約后的產(chǎn)生式進(jìn)行狀態(tài)轉(zhuǎn)化。
語(yǔ)法分析在一個(gè)分析狀態(tài)棧（或者分析狀態(tài)序列）上操作刺下。如果文本屬于這個(gè)語(yǔ)法的話绑嘹，移入的狀態(tài)最終會(huì)被規(guī)約為開(kāi)始符號(hào)。

語(yǔ)法分析表G算法如下：
輸入： 文法G
輸出：分析表
方法：

1. 構(gòu)造G的LR(1)項(xiàng)集族C={I₀, I₁,...I_n}橘茉。

2. 語(yǔ)法分析器的狀態(tài)i由I_i構(gòu)造得到工腋，狀態(tài)i按照下面規(guī)則構(gòu)建：

   • 如果[A -> α?aβ, b]，并且GOTO(I_i, a) = i_j, 那么將ACTION[i, a]設(shè)置為移入j("sj")畅卓。a必須是終結(jié)符擅腰。
   • 如果[A -> α?, a] 在 I_i中，且A不是開(kāi)始符號(hào)翁潘，那么將ACTION[i, a]設(shè)置為規(guī)約 A -> α ( "rn"趁冈，n是產(chǎn)生式的編號(hào) )。
   • 如果[S' -> S, $] 在I_i中拜马，那么將ACTION[i, $]設(shè)置為接受("acc")渗勘。

3. 狀態(tài)i對(duì)于各個(gè)非終結(jié)符號(hào)A的goto按照下面規(guī)則構(gòu)造：
   如果GOTO(I_i, A) = I_j, 那么 GOTO[i, A] = j

4. 所有沒(méi)按照2, 3條規(guī)則定義的分析表?xiàng)l目都設(shè)置為錯(cuò)誤。

5. 語(yǔ)法分析表的初始狀態(tài)是由 [S' -> ?S, $] 的項(xiàng)集構(gòu)造得到的狀態(tài)俩莽。

所以旺坠，項(xiàng)集族，狀態(tài)和輸入符號(hào)決定了這個(gè)表的構(gòu)造扮超。
輸入符號(hào)就是文法里面的終結(jié)符號(hào)(Terminal)和非終結(jié)符號(hào)(None Terminal)取刃。
狀態(tài)就簡(jiǎn)單理解為項(xiàng)集族里面的項(xiàng)集閉包(Item-sets Closure)的編號(hào)。

項(xiàng)集族(Item-sets Closure Collections)
項(xiàng)集族是由項(xiàng)集閉包組成的出刷，它是構(gòu)造出來(lái)的一個(gè)文法的狀態(tài)機(jī)的全部狀態(tài)璧疗。

項(xiàng)集閉包(Item-sets Closure)
一個(gè)項(xiàng)集閉包就是一個(gè)狀態(tài)，大概解釋就是在這個(gè)狀態(tài)上進(jìn)行輸入轉(zhuǎn)換可能用到的全部產(chǎn)生式組成的項(xiàng)馁龟。

項(xiàng)(Item)
標(biāo)準(zhǔn) LR(1)分析器的項(xiàng)是由產(chǎn)生式病毡，當(dāng)前位置和輸入字符構(gòu)成的。

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__())

實(shí)現(xiàn)了項(xiàng)屁柏，和相關(guān)的操作啦膜。因?yàn)樗陂]包中作為集合元素，所以實(shí)現(xiàn) __hash__ 淌喻， __eq__ 和 __ne__ 方法僧家，這樣集合就可以迭代。

from regex.parsing_table import Item
i1 = Item('S', 'b|c', 2, 'k')
i1
Out[4]: <Item: S -> b|.c      k >

項(xiàng)集閉包的實(shí)現(xiàn)

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包含所有的項(xiàng)裸删，label是這個(gè)閉包的狀態(tài)名八拱，這里規(guī)定為一個(gè)數(shù)字，goto是一個(gè)字典，用于記錄這個(gè)狀態(tài)在不同輸入的轉(zhuǎn)換目標(biāo)狀態(tài)肌稻。
__contains__ 用于計(jì)算項(xiàng)(Item)是否包含在這個(gè)閉包中清蚀。
因?yàn)殚]包還會(huì)包含在族(collection)中作為一個(gè)元素，所以也實(shí)現(xiàn) __eq__ 和 __hash__爹谭，這樣集合就可以作為一個(gè)迭代器 枷邪。

項(xiàng)集閉包的算法：
對(duì)于一個(gè)項(xiàng)集(Item-sets) I ，計(jì)算它的閉包 CLOSURE(I) 诺凡。

1. 將 I 中的各個(gè)項(xiàng)加入到閉包當(dāng)中东揣。
2. 閉包中的每個(gè)項(xiàng)， 如 [A -> α?Bβ, a]腹泌，對(duì)文法G中的每個(gè)非終結(jié)符B的產(chǎn)生式 B -> γ嘶卧，對(duì)FIRST(βa)中的每個(gè)終結(jié)符 b, 將 [B -> ?γ, b] 加入閉包當(dāng)中。

這里的?B是推理當(dāng)前位置后面可能出現(xiàn)的規(guī)約（B的產(chǎn)生式）凉袱，以及B規(guī)約結(jié)束之后芥吟，能夠在之后出現(xiàn)的終結(jié)符。

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

我們需要知道關(guān)于grammar和firsts的定義专甩。

grammar = [ ("stmt", ("if", "(", "C", ")", "S", "else", "S")),
             ...
          ]

grammar 在這里定義為一個(gè)產(chǎn)生式列表钟鸵。產(chǎn)生式是由一個(gè)頭部和體合成的元組，產(chǎn)生式的體本身也是一個(gè)元組配深。

firsts是為了計(jì)算一個(gè)產(chǎn)生式的體中可能出現(xiàn)的第一個(gè)終結(jié)符號(hào)携添，我們?cè)谝?guī)約時(shí)需要知道可能出現(xiàn)的下一個(gè)終結(jié)符號(hào)和應(yīng)該使用哪一個(gè)式子來(lái)進(jìn)行規(guī)約嫁盲。這樣我們?cè)谕茖?dǎo)的時(shí)候就能知道應(yīng)該進(jìn)入的狀態(tài)篓叶。

對(duì)于一個(gè)終結(jié)符號(hào)或者非終結(jié)符號(hào)， 它的first(X)算法如下：

1. X是終結(jié)符號(hào): first(X) = X
2. X是非終結(jié)符號(hào)：查找產(chǎn)生式 X -> Y₁Y₂...Y_k, 如果Y₁是非終結(jié)符且含有空產(chǎn)生式羞秤，那么 first(X) = first(Y₁) ∪ firsts(Y₂...Y_k), 否則就等于 first(Y₁),意思就是空產(chǎn)生式會(huì)形成多種可能性缸托，確定只有一個(gè)first的符號(hào)，后面的符號(hào)就排除掉了瘾蛋。如果Y是終結(jié)符號(hào)俐镐，就不用下推。如果Y是非終結(jié)符號(hào)哺哼，就考慮它是否產(chǎn)生空產(chǎn)生式佩抹，來(lái)決定考察下一個(gè)符號(hào)。
3. X是EPSILON: firsts(X) += EPSILON

具體的實(shí)現(xiàn)是這樣的：

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 分別判斷是否終結(jié)符號(hào)取董。
produce_epsilon 產(chǎn)生式的特殊形式棍苹，判斷是否一個(gè)空產(chǎn)生式。這里約定空產(chǎn)生式 N -> EPSILON 的體由 EPSILON 定義茵汰。
is_start_symbol 判斷是否開(kāi)始符號(hào)枢里。
first 計(jì)算一個(gè)終結(jié)符號(hào)或者非終結(jié)符號(hào)可能出現(xiàn)的第一個(gè)終結(jié)符。
firsts 計(jì)算一個(gè)句型（多個(gè)符號(hào)連在一起）可能出現(xiàn)的第一個(gè)終結(jié)符。

為求簡(jiǎn)單我們?cè)谶@里將 grammar, terminals, n_terminals 定義為列表栏豺。以后再實(shí)現(xiàn)如何將文法規(guī)則解析為python對(duì)象彬碱，和判斷是否終結(jié)符號(hào)的算法。

grammar = [("startsup", ("start")), 
           ("start", ("stmt")),
           ("stmt", ("if", "(", "C", ")", "S1", "else", "S2")),
          ]
terminals = ("if", "(", "C", ")", "S", "else", "S2", "$")
n_terminals = ("startsup", "start", "stmt")

實(shí)際上 C, S1, S2 都應(yīng)該是非終結(jié)符號(hào)奥洼。未來(lái)會(huì)替換為產(chǎn)生式巷疼，由編譯器規(guī)約它們的體來(lái)得到節(jié)點(diǎn)。

這個(gè)文法是對(duì)原文法進(jìn)行增廣后的增廣文法溉卓，由原來(lái)的產(chǎn)生式

• start -> stmt
• stmt -> if ( c ) S1 else S2

增加一個(gè)開(kāi)始符號(hào)start'和在尾部增加一個(gè)結(jié)束輸入$ , 對(duì)原來(lái)的詞法序列在尾部增加一個(gè)終結(jié)字符 $, 這樣當(dāng)掃描到最后一個(gè)字符為 $, 就進(jìn)入接受狀態(tài)皮迟。

• startsup -> start

這樣我們就實(shí)現(xiàn)了項(xiàng)集閉包的算法。

推導(dǎo)項(xiàng)集族

項(xiàng)集族C的算法：

1. 在C中桑寨，初始添加 [startsup -> ◆ start, $] 的項(xiàng) 【由Item('startsup', ('start',), 0, '$')構(gòu)造】伏尼，并計(jì)算閉包【get_closure(item)】為開(kāi)始狀態(tài)。
2. 在C中尉尾，對(duì)于每一個(gè)項(xiàng)集閉包I爆阶， 對(duì)于每一個(gè)文法符號(hào)X，可以是終結(jié)符號(hào)或者非終結(jié)符號(hào)沙咏，如果 goto(I, X) 非空且不在C中， 就加入到C中肢藐。

通過(guò)將每一個(gè)輸入可能得到的狀態(tài)加入到項(xiàng)集族故河，來(lái)完成構(gòu)建。
這里吆豹，goto(I,X)指的是狀態(tài) I 在輸入X下轉(zhuǎn)換到的狀態(tài)鱼的。(一個(gè)項(xiàng)集閉包）它的算法：

I中所有存在的項(xiàng) [A -> α?Xβ, a], 將 [A -> αX?β, a]加入到集合，并計(jì)算它的閉包痘煤。

實(shí)現(xiàn)如下：

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

得到了整個(gè)文法的項(xiàng)集族之后凑阶，我們就可以根據(jù)之前給出的構(gòu)建出語(yǔ)法分析表了。這里將終結(jié)符號(hào)的ACTION和非終結(jié)符號(hào)的GOTO拼接在一起衷快。并且沒(méi)有???♂?錯(cuò)誤處理宙橱，這里默認(rèn)將錯(cuò)誤動(dòng)作全部初始化為'.'。

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

這樣就得到了語(yǔ)法分析表蘸拔。

全部代碼在這里：

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

看下結(jié)果：

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   .         .      .     

語(yǔ)法分析和翻譯

語(yǔ)法分析

語(yǔ)法分析器在一個(gè)狀態(tài)棧上工作师郑，這個(gè)棧存儲(chǔ)了移入的狀態(tài)，它代表了已經(jīng)輸入调窍，尚未規(guī)約的詞法單元宝冕。語(yǔ)法分析器對(duì)token_stream(經(jīng)過(guò)詞法器解析后的代碼)的詞法單元逐個(gè)進(jìn)行4種操作。分析器在分析開(kāi)始前移入狀態(tài)0陨晶。分析器以狀態(tài)棧上的最后一個(gè)狀態(tài)（棧頂）為當(dāng)前狀態(tài)猬仁，并且根據(jù)輸入字符查分析表帝璧，來(lái)獲得當(dāng)前操作。

四種分析操作：

移入湿刽，將目標(biāo)狀態(tài)移入到狀態(tài)棧頂的烁。進(jìn)入下一個(gè)詞法單元。
規(guī)約诈闺，規(guī)約目標(biāo)產(chǎn)生式渴庆，當(dāng)前詞法單元不變群井，繼續(xù)查表進(jìn)行下一個(gè)操作剿骨，直到當(dāng)前詞法單狀態(tài)元被移入垦搬。
接受人柿，在含有增廣文法開(kāi)始符號(hào)產(chǎn)生式的項(xiàng) [startsup -> start◆, '$']，如果當(dāng)前輸入為 '$'鹃彻， 分析成功進(jìn)入接受狀態(tài)熙暴，并結(jié)束秒咨。
錯(cuò)誤卓缰， 目前我們忽略錯(cuò)誤處理计呈。

代碼如下：

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

它接受一個(gè)詞法單元流，并且分析征唬，如果分析成功捌显，accept就設(shè)置為T(mén)rue

from tokenizer import tokenizer
token_stream = tokenizer("if (C) S1 else S2")
sdt = SDT()
sdt.parse(token_stream)
sdt.accept
Out[8]: True

翻譯方案

翻譯方案一般插入到分析過(guò)程當(dāng)中。

每個(gè)非終結(jié)符號(hào)都會(huì)形成一個(gè)函數(shù)总寒，我們這里暫時(shí)在代碼中預(yù)定義好非終結(jié)符號(hào)的翻譯函數(shù)扶歪。

因?yàn)長(zhǎng)R分析器是從右到左規(guī)約，而在移入的時(shí)候并不判斷目前在哪個(gè)產(chǎn)生式的內(nèi)部摄闸，因此翻譯方案用后綴翻譯來(lái)實(shí)現(xiàn)善镰，就是在規(guī)約的時(shí)候翻譯。產(chǎn)生式頭部的名稱(chēng)作為函數(shù)名贪薪，規(guī)約的內(nèi)容作為參數(shù)來(lái)進(jìn)行調(diào)用媳禁，向上返回函數(shù)的結(jié)果眠副。

建立一個(gè)參數(shù)棧:

        self.arg_stack = []

token在移入的時(shí)候作為值移入到棧中画切。

        self.push_arg(token)

規(guī)約時(shí)，將值移出囱怕，作為規(guī)約函數(shù)的參數(shù)霍弹。返回的結(jié)果，就是非終結(jié)符號(hào)的值娃弓，移入到棧中典格。

        # 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屬性），對(duì)于繼承屬性并不適用台丛。比如 stmt -> if (C) S1 else S2 大致會(huì)形成如下翻譯方案:

    C.code
    S1.scode
    goto stmt.next
    label L1
    S2.code

其中耍缴，stmt.next 由外部傳入砾肺，是stmt作為產(chǎn)生式的體時(shí)的繼承屬性，LL分析器通過(guò)預(yù)測(cè)分析表已經(jīng)獲取了頭部防嗡，所以可以預(yù)先分配一個(gè)值变汪。這里由于分析器是規(guī)約方式的，因此尚不知道繼承屬性的值蚁趁。一般采取用一個(gè)空產(chǎn)生式來(lái)替代翻譯內(nèi)容并先生成繼承屬性的方法來(lái)解決裙盾，不過(guò)會(huì)帶來(lái)語(yǔ)法分析時(shí)的復(fù)雜性。

我們?cè)谶@里采用延遲調(diào)用的方法他嫡，就是 stmt 規(guī)約完成后并不直接返回翻譯的字符串值（因?yàn)檫€有一些屬性不知道）番官， 而是返回一個(gè)函數(shù)，通過(guò)將未知的內(nèi)容包裝成參數(shù)向上返回钢属，在進(jìn)行規(guī)約 start -> stmt 時(shí)徘熔， 再將start 生成的必要值作為參數(shù)來(lái)調(diào)用 stmt 規(guī)約的返回值，就可以獲得正確的翻譯方案了淆党。

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

添加對(duì)結(jié)束狀態(tài)的處理近顷，和一些其他必要?jiǎng)幼鳌＿@樣宁否，分析和翻譯方案就變成了：

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()

運(yùn)行一下窒升，

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

這是個(gè)簡(jiǎn)陋的過(guò)程，但是核心功能完整慕匠，我們可以在之后的過(guò)程中饱须，逐步完善它。
通常台谊，詞法規(guī)則和語(yǔ)法規(guī)則是由單獨(dú)的文件定義的蓉媳。所以需要對(duì)詞法規(guī)則和語(yǔ)法規(guī)則進(jìn)行解析的構(gòu)件，來(lái)完成從源文本到python對(duì)象的轉(zhuǎn)換锅铅。翻譯方案通常嵌入到語(yǔ)法規(guī)則中酪呻。
錯(cuò)誤處理可以在適當(dāng)?shù)那闆r引入到編譯過(guò)程當(dāng)中。
另外盐须，二義性文法玩荠，空產(chǎn)生式等情況的轉(zhuǎn)換在語(yǔ)法添加的過(guò)程當(dāng)中會(huì)浮現(xiàn)。
當(dāng)然還有為語(yǔ)法規(guī)則添加基本的語(yǔ)句贼邓，使之逐漸成為一個(gè)完善的編譯前端阶冈。

不論如何，我們已經(jīng)完成了編譯前端從源語(yǔ)言到目標(biāo)語(yǔ)言的全部流程塑径，是一個(gè)成功的開(kāi)始女坑。