-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpseudocode.txt
161 lines (124 loc) · 3.67 KB
/
pseudocode.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
Data structures:
token
type
text
rule
name
productions
repeating-segments
rule-references
min_count
max_count
grammar_table
token-references
actions
grammar_table-cell-reference
optional error code
symbol_table
parse_tree
abstract_syntax_tree
result
type
char_val
string_val
integer_val
double_val
enum_val
result_list
==================================
Phases:
- Scan(text): token_list
- Parse(token_list): parse_tree
- Annotate(parse_tree): abstract_syntax_tree
- Execute(abstract_syntax_tree): output
==================================
Parser generator:
foreach (nonterminal in grammar):
work_rules
work_rules:
foreach (rule in nonterminal):
if (rule is not in rule array):
foreach (node in rule):
if (node is a terminal):
add_leaf
if (there is a previous leaf):
amend_previous_leaf
else:
push rule -> rule array
follow node
add_leaf:
add row
if (column does not exist with this terminal):
create a column for this terminal
write cell to that column in new row
amend_previous_leaf:
if (previous leaf is higher in rules):
add "move se"
else if (previous leaf is lower in rules):
add "move ne"
else:
??? depending on associativity, do one of the above ???
==================================
Open Questions:
- Does the above work with indirect recursion?
- How do I find out whether a terminal is in a "higher" or "lower" rule?
Not included:
- Repetition
==================================
Grammar:
expr ::=
expr '+' term
| term
;
term ::= literal
;
Example:
1
1 + 2
3: gehe zu 4
4: folge "expr" -> 3
3: hier warst du schon, -> position danach pushen, gehe zu 5
5: folge "term" -> 8
8: "add leaf"; regel ist zu ende, daher pop -> 4
4: '+' -> "add leaf;" schreibe 'move ne' in vorherige zelle
4: folge "term" -> 8
8: "add leaf"; schreibe 'move se' in vorherige zelle (?); regel ist zu ende, daher pop -> 4
4: regel ist zu ende, stack ist leer, daher schreibe zeile für "$"
literal $ '+'
1
-----------------------------------------------------
2
-----------------------------------------------------
3
-----------------------------------------------------
4
Table:
literal '+' $ <--- current
===================================================
1 add leaf; ERROR ERROR
go 2
-----------------------------------------------------
2 ERROR move ne; END
add leaf;
go 3
-----------------------------------------------------
3 move se; ERROR ERROR
add leaf;
move back;
go 4
-----------------------------------------------------
4 ERROR move ne; END
add leaf;
go 3
-----------------------------------------------------
5
-----------------------------------------------------
6
Algorithmus:
1. Suche alle Terminals, und mache Spalten daraus
2. Suche alle Regeln, die mit Terminals beginnen
2.1. Alle diese bekommen einen Eintrag in der ersten Zeile
2.2. "Add leaf; go x", wobei x bei 2 beginnt und inkrementiert wird
2.3. Suche alle Regeln, die diese Regel beinhalten
Nach LINKS: Ist hier ein Terminal?
F"Move se; add leaf; move back; go x", wobei x die vorherige Zeile ist