parser.ll1() - Code Metrics - hatamiarash7/LL1_Parser - Measure and Improve Code Quality continuously with Scrutinizer

parser.ll1() C
last analyzed 2019-06-02 19:43 UTC

↳ Parent: parser

Complexity

Conditions

Size

Total Lines	28
Code Lines	21

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
eloc	21
dl	0
loc	28
rs	6.6666
c	0
b	0
f	0
cc	9
nop	2

import re

import pandas as pd


def parse(user_input, start_symbol, parsingTable):
    flag = 0

    user_input = user_input + "$"

    stack = []

    stack.append("$")
    stack.append(start_symbol)

    input_len = len(user_input)
    index = 0

    while len(stack) > 0:

        top = stack[len(stack) - 1]

        print("Top =>", top)

        current_input = user_input[index]

        print("Current_Input => ", current_input)

        if top == current_input:
            stack.pop()
            index = index + 1
        else:

            key = top, current_input
            print(key)

            if key not in parsingTable:
                flag = 1
                break

            value = parsingTable[key]
            if value != '@':
                value = value[::-1]
                value = list(value)

                stack.pop()

                for element in value:
                    stack.append(element)
            else:
                stack.pop()

    if flag == 0:
        print("String accepted!")
    else:
        print("String not accepted!")


def ll1(follow, productions):
    print("\nParsing Table\n")

    table = {}
    for key in productions:
        for value in productions[key]:
            if value != '@':
                for element in first(value, productions):
                    table[key, element] = value
            else:
                for element in follow[key]:
                    table[key, element] = value

    for key, val in table.items():
        print(key, "=>", val)

    new_table = {}
    for pair in table:
        new_table[pair[1]] = {}

    for pair in table:
        new_table[pair[1]][pair[0]] = table[pair]

    print("\n\nTable\n")
    print(pd.DataFrame(new_table).fillna('-'))
    print("\n")

    return table


def follow(s, productions, ans):
    if len(s) != 1:
        return {}

    for key in productions:
        for value in productions[key]:
            f = value.find(s)
            if f != -1:
                if f == (len(value) - 1):
                    if key != s:
                        if key in ans:
                            temp = ans[key]
                        else:
                            ans = follow(key, productions, ans)
                            temp = ans[key]
                        ans[s] = ans[s].union(temp)
                else:
                    first_of_next = first(value[f + 1:], productions)
                    if '@' in first_of_next:
                        if key != s:
                            if key in ans:
                                temp = ans[key]
                            else:
                                ans = follow(key, productions, ans)
                                temp = ans[key]
                            ans[s] = ans[s].union(temp)
                            ans[s] = ans[s].union(first_of_next) - {'@'}
                    else:
                        ans[s] = ans[s].union(first_of_next)
    return ans


def first(s, productions):
    c = s[0]
    ans = set()
    if c.isupper():
        for st in productions[c]:
            if st == '@':
                if len(s) != 1:
                    ans = ans.union(first(s[1:], productions))
                else:
                    ans = ans.union('@')
            else:
                f = first(st, productions)
                ans = ans.union(x for x in f)
    else:
        ans = ans.union(c)
    return ans


if __name__ == "__main__":
    productions = dict()
    grammar = open("grammar", "r")
    first_dict = dict()
    follow_dict = dict()
    flag = 1
    start = ""
    for line in grammar:
        l = re.split("( |->|\n|\||)*", line)
        lhs = l[0]
        rhs = set(l[1:-1]) - {''}
        if flag:
            flag = 0
            start = lhs
        productions[lhs] = rhs

    print('\nFirst\n')
    for lhs in productions:
        first_dict[lhs] = first(lhs, productions)
    for f in first_dict:
        print(str(f) + " : " + str(first_dict[f]))
    print("")

    print('\nFollow\n')

    for lhs in productions:
        follow_dict[lhs] = set()

    follow_dict[start] = follow_dict[start].union('$')

    for lhs in productions:
        follow_dict = follow(lhs, productions, follow_dict)

    for lhs in productions:
        follow_dict = follow(lhs, productions, follow_dict)

    for f in follow_dict:
        print(str(f) + " : " + str(follow_dict[f]))

    ll1Table = ll1(follow_dict, productions)

    # parse("edcc", start, ll1Table)
    parse("aabd", start, ll1Table)


1			import re
2
3			import pandas as pd
4
5
6			def parse(user_input, start_symbol, parsingTable):
7			flag = 0
8
9			user_input = user_input + "$"
10
11			stack = []
12
13			stack.append("$")
14			stack.append(start_symbol)
15
16			input_len = len(user_input)
17			index = 0
18
19			while len(stack) > 0:
20
21			top = stack[len(stack) - 1]
22
23			print("Top =>", top)
24
25			current_input = user_input[index]
26
27			print("Current_Input => ", current_input)
28
29			if top == current_input:
30			stack.pop()
31			index = index + 1
32			else:
33
34			key = top, current_input
35			print(key)
36
37			if key not in parsingTable:
38			flag = 1
39			break
40
41			value = parsingTable[key]
42			if value != '@':
43			value = value[::-1]
44			value = list(value)
45
46			stack.pop()
47
48			for element in value:
49			stack.append(element)
50			else:
51			stack.pop()
52
53			if flag == 0:
54			print("String accepted!")
55			else:
56			print("String not accepted!")
57
58
59			def ll1(follow, productions):
60			print("\nParsing Table\n")
61
62			table = {}
63			for key in productions:
64			for value in productions[key]:
65			if value != '@':
66			for element in first(value, productions):
67			table[key, element] = value
68			else:
69			for element in follow[key]:
70			table[key, element] = value
71
72			for key, val in table.items():
73			print(key, "=>", val)
74
75			new_table = {}
76			for pair in table:
77			new_table[pair[1]] = {}
78
79			for pair in table:
80			new_table[pair[1]][pair[0]] = table[pair]
81
82			print("\n\nTable\n")
83			print(pd.DataFrame(new_table).fillna('-'))
84			print("\n")
85
86			return table
87
88
89			def follow(s, productions, ans):
90			if len(s) != 1:
91			return {}
92
93			for key in productions:
94			for value in productions[key]:
95			f = value.find(s)
96			if f != -1:
97			if f == (len(value) - 1):
98			if key != s:
99			if key in ans:
100			temp = ans[key]
101			else:
102			ans = follow(key, productions, ans)
103			temp = ans[key]
104			ans[s] = ans[s].union(temp)
105			else:
106			first_of_next = first(value[f + 1:], productions)
107			if '@' in first_of_next:
108			if key != s:
109			if key in ans:
110			temp = ans[key]
111			else:
112			ans = follow(key, productions, ans)
113			temp = ans[key]
114			ans[s] = ans[s].union(temp)
115			ans[s] = ans[s].union(first_of_next) - {'@'}
116			else:
117			ans[s] = ans[s].union(first_of_next)
118			return ans
119
120
121			def first(s, productions):
122			c = s[0]
123			ans = set()
124			if c.isupper():
125			for st in productions[c]:
126			if st == '@':
127			if len(s) != 1:
128			ans = ans.union(first(s[1:], productions))
129			else:
130			ans = ans.union('@')
131			else:
132			f = first(st, productions)
133			ans = ans.union(x for x in f)
134			else:
135			ans = ans.union(c)
136			return ans
137
138
139			if __name__ == "__main__":
140			productions = dict()
141			grammar = open("grammar", "r")
142			first_dict = dict()
143			follow_dict = dict()
144			flag = 1
145			start = ""
146			for line in grammar:
147			l = re.split("( \|->\|\n\|\\|\|)*", line)
148			lhs = l[0]
149			rhs = set(l[1:-1]) - {''}
150			if flag:
151			flag = 0
152			start = lhs
153			productions[lhs] = rhs
154
155			print('\nFirst\n')
156			for lhs in productions:
157			first_dict[lhs] = first(lhs, productions)
158			for f in first_dict:
159			print(str(f) + " : " + str(first_dict[f]))
160			print("")
161
162			print('\nFollow\n')
163
164			for lhs in productions:
165			follow_dict[lhs] = set()
166
167			follow_dict[start] = follow_dict[start].union('$')
168
169			for lhs in productions:
170			follow_dict = follow(lhs, productions, follow_dict)
171
172			for lhs in productions:
173			follow_dict = follow(lhs, productions, follow_dict)
174
175			for f in follow_dict:
176			print(str(f) + " : " + str(follow_dict[f]))
177
178			ll1Table = ll1(follow_dict, productions)
179
180			# parse("edcc", start, ll1Table)
181			parse("aabd", start, ll1Table)
182

hatamiarash7 / LL1_Parser

parser.ll1() C last analyzed 2019-06-02 19:43 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

parser.ll1() C
last analyzed 2019-06-02 19:43 UTC