Bottom-Up Parsing - Revision history

Root: /* Building LALR(1) Parse Tables */

2026-04-26T19:12:23Z

Building LALR(1) Parse Tables

← Older revision		Revision as of 19:12, 26 April 2026
Line 140:		Line 140:
	== Building LALR(1) Parse Tables ==		== Building LALR(1) Parse Tables ==

	The ~~following~~ video presents the complete process of building a parser.		The video presents the complete process of building a parser.

	The grammar is the one from [[Bottom-Up Parsing/Exercise 9: LALR(1)\|Exercise 9: LALR(1)]] (also below).		The grammar is the one from [[Bottom-Up Parsing/Exercise 9: LALR(1)\|Exercise 9: LALR(1)]] (also below).

	~~<runphp>~~		[https://www.youtube.com/embed/qdFUxuRLDeg video]
	~~echo<<<___EOT___~~
	~~<iframe width="560" height="315" src="~~https://www.youtube.com/embed/qdFUxuRLDeg~~" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>~~
	~~___EOT___;~~
	~~</runphp>~~

	== Compacting Parse Tables ==		== Compacting Parse Tables ==

Root: /* The Parse Table */

2024-05-02T09:32:27Z

The Parse Table

← Older revision		Revision as of 09:32, 2 May 2024
Line 125:		Line 125:
	Assuming that the DFA has been built and, thus, the '''I<sub>0</sub> ... I<sub>n</sub>''' states are known, the following steps produce the parse table:		Assuming that the DFA has been built and, thus, the '''I<sub>0</sub> ... I<sub>n</sub>''' states are known, the following steps produce the parse table:
	# State '''i''' is corresponds to '''I<sub>i</sub>'''; the corresponding actions are:		# State '''i''' is corresponds to '''I<sub>i</sub>'''; the corresponding actions are:
	#* If '''[~~A->α•aβ~~]''' ('''a''' is a terminal) is in '''I<sub>i</sub>''' and '''goto(I<sub>i</sub>,a) = I<sub>j</sub>''', then define '''action[i,a] = shift j'''		#* If '''[A→α•aβ]''' ('''a''' is a terminal) is in '''I<sub>i</sub>''' and '''goto(I<sub>i</sub>,a) = I<sub>j</sub>''', then define '''action[i,a] = shift j'''
	#* If '''[~~A->α•~~]''' is in '''I<sub>i</sub>''', then define '''action[i,a] = reduce ~~A->α~~''' for all '''α ∈ FOLLOW(A)''' ('''A≠S'''', '''S'''' being the start symbol)		#* If '''[A→α•]''' is in '''I<sub>i</sub>''', then define '''action[i,a] = reduce A→α''' for all '''α ∈ FOLLOW(A)''' ('''A≠S'''', '''S'''' being the start symbol)
	#* If '''[S'~~->S•~~$]''' ('''S'''' being the start symbol) is in '''I<sub>i</sub>''', then define '''action[i,$] = ACCEPT'''		#* If '''[S'→S•$]''' ('''S'''' being the start symbol) is in '''I<sub>i</sub>''', then define '''action[i,$] = ACCEPT'''
	# For state '''i''' and '''A''' a non-terminal symbol, define '''goto(i,A) = j''' if '''goto(I<sub>i</sub>, A) = I<sub>j</sub>'''		# For state '''i''' and '''A''' a non-terminal symbol, define '''goto(i,A) = j''' if '''goto(I<sub>i</sub>, A) = I<sub>j</sub>'''

Root: /* Building the DFA */

2024-05-02T09:31:07Z

Building the DFA

← Older revision		Revision as of 09:31, 2 May 2024
Line 100:		Line 100:
	Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):		Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):

	I0 = E' → •E$ I1 = E' → E•$ I5 = F → (•E) I6 = F → id• I4 = T → T*•F I11 = E → E+T•		I0 = E' → •E$ I1 = E' → E•$ I5 = F → (•E) I6 = F → id• I4 = T → T*•F I11 = E → E+T•
	E → •E+T E → E•+T E → •E+T F → •(E) T → T•*F		E → •E+T E → E•+T E → •E+T F → •(E) T → T•*F
	E → •T E → •T I2 = E → E+•T F → •id		E → •T E → •T I2 = E → E+•T F → •id

Root: /* Building the DFA */

2024-05-02T09:29:58Z

Building the DFA

← Older revision		Revision as of 09:29, 2 May 2024
Line 100:		Line 100:
	Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):		Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):

	I0 = E' → •E$ I1 = E' → E•$ I5 = F → (•E) I6 = F → id• I4 = T → T*•F I11 = E → E+T•		I0 = E' → •E$ I1 = E' → E•$ I5 = F → (•E) I6 = F → id• I4 = T → T*•F I11 = E → E+T•
	E → •E+T E → E•+T E → •E+T F → •(E) T → T•*F		E → •E+T E → E•+T E → •E+T F → •(E) T → T•*F
	E → •T E → •T I2 = E → E+•T F → •id		E → •T E → •T I2 = E → E+•T F → •id
	T → •TF I3 = E → T• T → •TF T → •TF I8 = T → TF•		T → •TF I3 = E → T• T → •TF T → •TF I8 = T → TF•
	T → •F T → T•*F T → •F T → •F I9 = F → (E•)		T → •F T → T•*F T → •F T → •F I9 = F → (E•)
	F → •(E) F → •(E) F → •(E) E → E•+T I10 = F → (E)•		F → •(E) F → •(E) F → •(E) E → E•+T I10 = F → (E)•
	F → •id I7 = T → F• F → •id F → •id		F → •id I7 = T → F• F → •id F → •id


	Graphically:		Graphically:

Root: /* Building the DFA */

2024-05-02T09:27:55Z

Building the DFA

← Older revision		Revision as of 09:27, 2 May 2024
Line 100:		Line 100:
	Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):		Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):

	I0 = E'->•E$ I1 = E'->E•$ I5 = F->(•E) I6 = F->id• I4 = T->T*•F I11 = E->E+T•		I0 = E' → •E$ I1 = E' → E•$ I5 = F → (•E) I6 = F → id• I4 = T → T*•F I11 = E → E+T•
	E ->•E+T E ->E•+T E->•E+T F->•(E) T->T•*F		E → •E+T E → E•+T E → •E+T F → •(E) T → T•*F
	E ->•T E->•T I2 = E->E+•T F->•id		E → •T E → •T I2 = E → E+•T F → •id
	T ->•TF I3 = E ->T• T->•TF T->•TF I8 = T->TF•		T → •TF I3 = E → T• T → •TF T → •TF I8 = T → TF•
	T ->•F T ->T•*F T->•F T->•F I9 = F->(E•)		T → •F T → T•*F T → •F T → •F I9 = F → (E•)
	F ->•(E) F->•(E) F->•(E) E->E•+T I10 = F->(E)•		F → •(E) F → •(E) F → •(E) E → E•+T I10 = F → (E)•
	F ->•id I7 = T ->F• F->•id F->•id		F → •id I7 = T → F• F → •id F → •id

	Graphically:		Graphically:

Root: /* Building the DFA */

2024-05-02T09:24:57Z

Building the DFA

← Older revision		Revision as of 09:24, 2 May 2024
Line 76:		Line 76:
	=== Building the DFA ===		=== Building the DFA ===

	The DFA (a set of sets) starts by containing a single element, consisting of the set obtained by computing the ε-closure of the singular set '''{[S'~~->•S~~$]}''' ('''S''' is the start symbol):		The DFA (a set of sets) starts by containing a single element, consisting of the set obtained by computing the ε-closure of the singular set '''{[S'→•S$]}''' ('''S''' is the start symbol):

	DFA = { ε-closure({[S'~~->•S~~$]}) }		DFA = { ε-closure({[S'→•S$]}) }

	Then, repeat until it is not possible to add any further elements: for each element (set) '''I''' in the DFA and for each grammar symbol '''X''', add '''goto(I,X)''' (if not empty) to the DFA.		Then, repeat until it is not possible to add any further elements: for each element (set) '''I''' in the DFA and for each grammar symbol '''X''', add '''goto(I,X)''' (if not empty) to the DFA.
Line 86:		Line 86:
	Considering the grammar above, the initial configuration is:		Considering the grammar above, the initial configuration is:

	DFA = {I0} = {ε-closure({[E'~~->•E~~$]})}		DFA = {I0} = {ε-closure({[E'→•E$]})}

	With:		With:

	I0 = E'->•E$		I0 = E'→ •E$
	E ->•E+T		E → •E+T
	E ->•T		E → •T
	T ->•T*F		T → •T*F
	T ->•F		T → •F
	F ->•(E)		F → •(E)
	F ->•id		F → •id

	Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):		Then, applying the goto function as described above (essentially, we will look only to the symbols immediately in front of the dot), we get the following sets in the DFA (its states):

Root: /* Goto */

2024-05-02T09:22:57Z

Goto

← Older revision		Revision as of 09:22, 2 May 2024
Line 71:		Line 71:
	Example:		Example:

	I = {[E'~~->E•~~$], [~~E->E•~~+T]}		I = {[E'→E•$], [E→E•+T]}
	goto(I,+) = ε-closure({[~~E->E~~+•T]}) = {[~~E->E~~+•T], [~~T->•T~~*F], [~~T->•F~~], [~~F->•~~(E)], [~~F->•id~~]}		goto(I,+) = ε-closure({[E→E+•T]}) = {[E→E+•T], [T→•T*F], [T→•F], [F→•(E)], [F→•id]}

	=== Building the DFA ===		=== Building the DFA ===

Root: /* Building SLR Parse Tables */

2024-05-02T09:21:14Z

Building SLR Parse Tables

← Older revision		Revision as of 09:21, 2 May 2024
Line 32:		Line 32:
	S'→ S $		S'→ S $

	This rule indicates that when '''S''' (the start symbol) is reduced, then the input should be accepted, i.e., we would go from item '''S'~~->•S~~$''' to item '''S'~~->S•~~$'''.		This rule indicates that when '''S''' (the start symbol) is reduced, then the input should be accepted, i.e., we would go from item '''S'→•S$''' to item '''S'→S•$'''.

	Like for lexical analyzers, we will define two primitive functions: '''ε-closure''' and '''goto''' (similar to "move"), that will allow us to describe an algorithm for building the DFA.		Like for lexical analyzers, we will define two primitive functions: '''ε-closure''' and '''goto''' (similar to "move"), that will allow us to describe an algorithm for building the DFA.
Line 58:		Line 58:
	Then:		Then:

	I = {[E'~~->•E~~$]}		I = {[E'→•E$]}
	ε-closure(I) = {[E'~~->•E~~$], [~~E->•E~~+T], [~~E->•T~~], [~~T->•T~~*F], [~~T->•F~~], [~~F->•~~(E)], [~~F->•id~~]}		ε-closure(I) = {[E'→•E$], [E→•E+T], [E→•T], [T→•T*F], [T→•F], [F→•(E)], [F→•id]}

	=== Goto ===		=== Goto ===
Line 65:		Line 65:
	The goto function is formally defined as '''goto(I,X)''' ('''I''' is a set of LR(0) items, and '''X''' is a grammar symbol).		The goto function is formally defined as '''goto(I,X)''' ('''I''' is a set of LR(0) items, and '''X''' is a grammar symbol).

	goto(I,X) = ε-closure({[~~A->αX•β~~]: ∀[~~A->α•Xβ~~]∈I})		goto(I,X) = ε-closure({[A→αX•β]: ∀[A→α•Xβ]∈I})

	Informally, if '''γ''' was a viable prefix for the elements of '''I''', then '''γX''' is a viable prefix for the elements of '''goto(I,X)'''.		Informally, if '''γ''' was a viable prefix for the elements of '''I''', then '''γX''' is a viable prefix for the elements of '''goto(I,X)'''.

Root: /* Building SLR Parse Tables */

2024-05-02T09:19:21Z

Building SLR Parse Tables

← Older revision		Revision as of 09:19, 2 May 2024
Line 17:		Line 17:
	For instance:		For instance:

	E -> • A B C		E → • A B C
	E -> A • B C		E → A • B C

	Internally, the parser may use a pair of integers for representing an item (one for the rule, another for the dot's position).		Internally, the parser may use a pair of integers for representing an item (one for the rule, another for the dot's position).
Line 30:		Line 30:
	The first step is to build the augmented grammar. This is a grammar like the original, but with an additional rule '''S'''' ('''S''' is the start symbol):		The first step is to build the augmented grammar. This is a grammar like the original, but with an additional rule '''S'''' ('''S''' is the start symbol):

	S' -> S $		S'→ S $

	This rule indicates that when '''S''' (the start symbol) is reduced, then the input should be accepted, i.e., we would go from item '''S'->•S$''' to item '''S'->S•$'''.		This rule indicates that when '''S''' (the start symbol) is reduced, then the input should be accepted, i.e., we would go from item '''S'->•S$''' to item '''S'->S•$'''.
Line 40:		Line 40:
	Consider '''I''' a set of LR(0) items. The following conditions apply to rules in '''ε-closure(I)''':		Consider '''I''' a set of LR(0) items. The following conditions apply to rules in '''ε-closure(I)''':
	# Initially, all elements of '''I''' are in '''ε-closure(I)'''		# Initially, all elements of '''I''' are in '''ε-closure(I)'''
	# If '''~~A->α•Bβ~~''' is in '''ε-closure(I)''' and '''~~B->γ~~''' is a production, the add '''~~B->•γ~~''' to '''ε-closure(I)'''		# If '''A→α•Bβ''' is in '''ε-closure(I)''' and '''B→γ''' is a production, the add '''B→•γ''' to '''ε-closure(I)'''

	(repeat until the ε-closure(I) is unchanged)		(repeat until the ε-closure(I) is unchanged)
Line 48:		Line 48:
	Consider the following grammar (rule 0 corresponds to the augmented grammar):		Consider the following grammar (rule 0 corresponds to the augmented grammar):

	0) E' -> E $		0) E' → E $
	1) E -> E + T		1) E → E + T
	2) E -> T		2) E → T
	3) T -> T * F		3) T → T * F
	4) T -> F		4) T → F
	5) F -> ( E )		5) F → ( E )
	6) F -> id		6) F → id

	Then:		Then:

Root: /* Exercises: LALR(1) */

2023-05-24T17:26:26Z

Exercises: LALR(1)

← Older revision		Revision as of 17:26, 24 May 2023
Line 197:		Line 197:
	* [[Bottom-Up Parsing/Exercise 15: LALR(1)\|Exercise 15: LALR(1)]]: '''A → A M''' etc.		* [[Bottom-Up Parsing/Exercise 15: LALR(1)\|Exercise 15: LALR(1)]]: '''A → A M''' etc.
	* [[Bottom-Up Parsing/Exercise 16: LALR(1)\|Exercise 16: LALR(1)]]: '''R → R X b''' etc.		* [[Bottom-Up Parsing/Exercise 16: LALR(1)\|Exercise 16: LALR(1)]]: '''R → R X b''' etc.
	* [[Bottom-Up Parsing/Exercise 17: LALR(1)\|Exercise 17: LALR(1)]]:		* [[Bottom-Up Parsing/Exercise 17: LALR(1)\|Exercise 17: LALR(1)]]: '''X → X Y c''' etc.

	[[category:Compiladores]]		[[category:Compiladores]]