编译原理——LL（1）文法的判定

编程入门行业动态更新时间:2024-10-19 22:27:02

大概步骤

LL（1）文法的判定

准备工作

数据结构：本次实验选用python语言进行编程，主要用到的数据结构为字典。因其键值对一一对应较为方便，适合模拟LL（1）文法产生式左部和右部的对应关系。对于同一个非终结符多次出现在产生式左部的情况，本次实验采取的策略是用列表作为该键的值，这样便可以实现“一对多”的关系。

任务一计算First

求解每个符号的First集：遍历所有符号，当该符号为终结符时，其First集仅有它自己这一个元素。否则如果是非终结符，先判断其是否能推出ε，如果能则将ε加入该符号的First集。接着，对以该终结符为左部的产生式的右部串进行扫描，判断该串的第一个符号，如果符号为终结符，则将此终结符加入First集。至此，我们可以得到所有能推出ε和直接推出终结符的First集。

接下来处理不能直接推出的情况。对每个非终结符，遍历对应产生式右部的每个符号，将每个符号的First集并入此非终结符的First集直到遇到第一个不能推出空串ε的非终结符为止。这里对空串ε的处理方法是：开始遍历每个非终结符时，设置一个标记all_null，并初始化为1，仅当遇到第一个不能推出空串ε的非终结符时，将all_null置为0，并不再判断该串后面的符号。值得注意的是，每次合并First集合时，并不把空串合并进去，当一个右部串判断结束后再判断all_null的值，如果all_null为1，则把空串ε加入First集。后面将多次用到all_null标记，思想较为相似，不再赘述。

这里还有一个问题，在进行取并集时，由于数据结构用的是列表，会有重复元素，因此要进行消重。这在后面也多次用到。

任务二计算每个产生式右部的First集

求解每个产生式右部的First集：这里求解思路和求每个符号的First差不多，主要需要注意的地方当遇到第一个不能推出空串得非终结符时，停止后续符号的判断。这里也用到all_null进行控制，并且同样需要消重。

任务二计算Follow

6．求解每个非终结符的Follow集：第一步，需要把“#”放入开始符号“S”的Follow集中。接下来主要思想是找到每一非终结符所在串的下一个符号的First集，这里有几种特殊情况：（1）终结符为位于串尾，此时要将左部的Follow集并入该终结符的Follow集；（2）下一个符号推出空串ε，此时需要把下一个的后一个非终结符的Follow并入。注意：Follow集中不能出现空串ε。在代码实现上，可以把该非终结符后面所有的非终结符的Follow都并入Follow中，直到遇到串中的一个非终结符不能推出空串ε。这种合并…直到…的思想前面已经多次用到，可以是代码更简洁。最后再把所有的空串ε移除Follow集。消重不再赘述。

任务三计算Select

求解每个产生式的Select集：求解出所有的First集和Follow后，可以直接利用公式得到Select。

任务四判断

判断是否为LL（1）文法：最后一步进行判断，设置标记LL_1初始化为1，当交集不为空时LL_1置为0，得到最终判断结果。

总之，本次实验编码过程并不难，只需要注意一些细节和技巧，更为重要的是理解LL（1）文法判定的每一步思想，要真正地理解非终结符的First集和Follow集的意义是当词法分析遇到该非终结符时，下一步能够推得的终结符是哪些，进一步理解寻找Select交集的原因是遇到同一个终结符时，选择产生式会不会有多个产生式可选的冲突。如果要进一步探索本实验，可以增加第一步判断空串ε，还可以实现输入任意的上下文无关文法，判断其是否为LL（1）文法。

源代码

// An highlighted block
G = {'S': ['AB', 'bC'], 'A': ['ε', 'b'], 'B': ['ε', 'aD'], 'C': ['AD', 'b'], 'D': ['aS', 'c']}   # G[S]
non_terminal = ['S', 'A', 'B', 'C', 'D']  # non_terminal
terminal = ['a', 'b', 'c']    # terminal
null = 'ε'  # null string
First = {}
right_First = {}
print("G[S]:")
for left in G:
    for i in range(len(G[left])):
        print(left, '->', G[left][i])

# ============================== First Sets ========================================
for char in non_terminal+terminal:
    First[char] = []
    if char in terminal:               # terminal char itself belongs to First(char)
        First[char].append(char)
    for left in G:
        if left == char:
            if null in G[left]:            # X-> ε
                First[char].append(null)
            for i in range(len(G[left])):
                if G[left][i][0] in terminal:  # X-> a...
                    First[char].append(G[left][i][0])

for char in non_terminal:
    for right_null in G[char]:
        right = [r for r in right_null if r != null]
        all_null = 1
        for j in right:
            if null in First[j]:
                First[j].remove(null)
                First[char] += First[j]
                First[j].append(null)
            else:
                First[char] += First[j]   # the first char that cannot deduce ε
                all_null = 0              # all_null flag becomes 0
                break
        if all_null:     # if every char can deduce ε, then append ε in First[char]
            First[char].append(null)
    redundancy = []
    for x in First[char]:        # eliminate redundancy
        if x not in redundancy:
            redundancy.append(x)
    First[char] = redundancy
print("==================First sets======================")
for key in First:
    print('First', '(', key, ')', '=', set(First[key]))

# ============================== right_First Sets ========================================
for left in G:
    for right in G[left]:
        right_First[right] = []
        all_null = 1  # assume that all characters in right section can deduce ε
        if right == null:           # right section α = ε
            right_First[right].append(null)
        else:
            if null not in First[right[0]]:
                right_First[right] = First[right[0]]
            else:
                for i in range(len(right)):
                    right_First[right] += First[right[i]]
                    if null not in First[right[i]]:  # when find one character that cannot deduce ε, set all_null = 0
                        all_null = 0
                        break
        redundancy = []
        for x in right_First[right]:  # eliminate redundancy
            if x not in redundancy:
                redundancy.append(x)
        right_First[right] = redundancy
        if not all_null:             # if not all_null, remove 'ε'
            right_First[right].remove(null)

print("==================right_First sets======================")
for right in right_First:
    print('First', '(', right, ')', '=', set(right_First[right]))

# ============================== Follow Sets ========================================
Follow = {}
for char in non_terminal:
    Follow[char] = []
    if char == 'S':     # S is the start character
        Follow[char].append('#')
    else:
        for left in G:
            for right in G[left]:
                all_null = 1        # assume that all characters in right section can deduce ε
                if char == right[-1]:
                    Follow[char] += Follow[left]
                else:
                    if char in right:
                        for i in range(right.index(char) + 1, len(right)):  # check the remainder after char
                            Follow[char] += First[right[i]]
                            if null not in First[right[i]]:    # when find one character cannot deduce ε
                                all_null = 0                   # set all_null = 0
                                break
                        if all_null:                           # if all_null, add Follow[leftSection]
                            Follow[char] += Follow[left]

    redundancy = []
    for x in Follow[char]:  # eliminate redundancy
        if x not in redundancy:
            redundancy.append(x)
    Follow[char] = [f for f in redundancy if f != null]
print("==================Follow sets======================")
for left in Follow:
    print('Follow', '(', left, ')', '=', set(Follow[left]))

# ============================== Select Sets ========================================
Select = {}
for left in G:
    for right in G[left]:
        key = left + '->' + right
        Select[key] = []
        if null not in right_First[right]:
            Select[key] = right_First[right]
        else:
            Select[key] = [s for s in right_First[right] if s != null] + Follow[left]
print("==================Select sets======================")
for generator in Select:
    print('Select', '(', generator, ')', '=', set(Select[generator]))

# ============================== Judgement of LL(1) ========================================
intersection = {}
for left in G:
    intersection[left] = []
    union = []
    for right in G[left]:
        generator = left + '->' + right
        for s in Select[generator]:
            if s not in union:
                union.append(s)
            else:
                intersection[left].append(s)
LL_1 = 1
for left in intersection:
    if len(intersection[left]) == 0:
        intersection[left] = 'Φ'
    else:
        intersection[left] = set(intersection[left])
        LL_1 = 0
print("==================Judgement of LL(1)======================")
for left in G:
    generator_1 = left + '->' + G[left][0]
    generator_2 = left + '->' + G[left][1]
    print('Select', '(', generator_1, ')', '∩', 'Select', '(', generator_2, ')', '=', intersection[left])
if LL_1:
    print("The intersection is Φ, so the G[s] belongs to LL(1) grammar!")
else:
    print("The intersection is not  Φ, so the G[s] does not belong to LL(1) grammar!")