Bottom-Up Parsing - Revision history

Root: Redirected page to ist:Bottom-Up Parsing

2018-12-06T18:06:00Z

Redirected page to ist:Bottom-Up Parsing

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

2016-04-21T13:47:40Z

Exercises: LALR(1)

← Older revision		Revision as of 13:47, 21 April 2016
Line 153:		Line 153:
	* [[Bottom-Up Parsing/Example 3: SLR(1)\|Example 3: SLR(1)]]		* [[Bottom-Up Parsing/Example 3: SLR(1)\|Example 3: SLR(1)]]
	* [[Bottom-Up Parsing/Example 4: LALR(1)\|Example 4: LALR(1)]]		* [[Bottom-Up Parsing/Example 4: LALR(1)\|Example 4: LALR(1)]]
	* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)		<!--* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)-->
	* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06		* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06
	* [[Bottom-Up Parsing/Exercise 6: LALR(1)\|Example 6: LALR(1)]] - appeared in Test 2, 2015/06/19		* [[Bottom-Up Parsing/Exercise 6: LALR(1)\|Example 6: LALR(1)]] - appeared in Test 2, 2015/06/19
	* [[Bottom-Up Parsing/Exercise 7: LALR(1)\|Example 7: LALR(1)]] - appeared in Test 2, 2015/06/19		* [[Bottom-Up Parsing/Exercise 7: LALR(1)\|Example 7: LALR(1)]] - appeared in Test 2, 2015/06/19
			* [[Bottom-Up Parsing/Exercise 8: LALR(1)\|Exercise 8: LALR(1)]] - '''S -> G b b''' etc.
			* [[Bottom-Up Parsing/Exercise 9: LALR(1)\|Exercise 9: LALR(1)]] - '''E -> [ E ; L ]''' etc.
			* [[Bottom-Up Parsing/Exercise 10: LALR(1)\|Exercise 10: LALR(1)]] - '''S -> i S''' etc.
			* [[Bottom-Up Parsing/Exercise 11: LALR(1)\|Exercise 11: LALR(1)]] - '''A -> B y y''' etc.
			* [[Bottom-Up Parsing/Exercise 12: LALR(1)\|Exercise 12: LALR(1)]] - '''A -> B x y''' etc.
			* [[Bottom-Up Parsing/Exercise 13: LALR(1)\|Exercise 13: LALR(1)]] - '''A -> A B A x''' etc.

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

2015-06-22T13:02:48Z

Exercises: LALR(1)

← Older revision		Revision as of 13:02, 22 June 2015
Line 155:		Line 155:
	* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)		* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)
	* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06		* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06
			* [[Bottom-Up Parsing/Exercise 6: LALR(1)\|Example 6: LALR(1)]] - appeared in Test 2, 2015/06/19
			* [[Bottom-Up Parsing/Exercise 7: LALR(1)\|Example 7: LALR(1)]] - appeared in Test 2, 2015/06/19

Root: /* Examples and Exercises */

2015-02-09T16:02:45Z

Examples and Exercises

← Older revision		Revision as of 16:02, 9 February 2015
Line 141:		Line 141:
	== Compacting Parse Tables ==		== Compacting Parse Tables ==

	== ~~Examples and~~ Exercises ==		== Exercises: SLR(1) ==

			* [[Bottom-Up Parsing/SLR(1) Exercise 01]]
			* [[Bottom-Up Parsing/SLR(1) Exercise 02]]
			* [[Bottom-Up Parsing/SLR(1) Exercise 03]]

			== Exercises: LALR(1) ==

	* [[Bottom-Up Parsing/LALR(1) Example 1\|LALR(1) Example 1]]		* [[Bottom-Up Parsing/LALR(1) Example 1\|LALR(1) Example 1]]

Root at 07:51, 28 June 2012

2012-06-28T07:51:18Z

← Older revision		Revision as of 07:51, 28 June 2012
Line 6:		Line 6:

	The sections below describe, first, the LR(0) and SLR(1) algorithms, and then, the LALR(1) algorithm. All three parsers share the same "shift" and "goto" entries, but differ in the restrictions put on "reduce" actions.		The sections below describe, first, the LR(0) and SLR(1) algorithms, and then, the LALR(1) algorithm. All three parsers share the same "shift" and "goto" entries, but differ in the restrictions put on "reduce" actions.

			If the parse table contains conflicts, the grammar is said not to belong to that class, e.g., a grammar is said to be SLR(1) if its SLR(1) parse table does not contain any conflicts.

	== Building SLR Parse Tables ==		== Building SLR Parse Tables ==

Root: /* Examples and Exercises */

2012-06-05T12:32:16Z

Examples and Exercises

← Older revision		Revision as of 12:32, 5 June 2012
Line 146:		Line 146:
	* [[Bottom-Up Parsing/Example 4: LALR(1)\|Example 4: LALR(1)]]		* [[Bottom-Up Parsing/Example 4: LALR(1)\|Example 4: LALR(1)]]
	* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)		* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)
			* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06

Root: /* The Parse Table */

2012-04-17T09:00:45Z

The Parse Table

← Older revision		Revision as of 09:00, 17 April 2012
Line 133:		Line 133:
	Considering our example grammar, the following parse table would result from applying the steps above:		Considering our example grammar, the following parse table would result from applying the steps above:

	[[Image:bupslrtable.png]]		[[Image:bupslrtable.png\|400px]]

	== Building LALR(1) Parse Tables ==		== Building LALR(1) Parse Tables ==

Root: /* The Parse Table */

2012-04-17T08:49:37Z

The Parse Table

← Older revision		Revision as of 08:49, 17 April 2012
Line 129:		Line 129:
	All cells left empty correspond to syntax errors.		All cells left empty correspond to syntax errors.

	If step 1 above produces cells with multiple values, then the grammar is said not to be SLR(1) ~~(in general, a~~ grammar is said to be SLR(1) if an SLR(1) parser can be built).		If step 1 above produces cells with multiple values, i.e., a shift and a reduce or more than one reduce, then the parse table has action conflicts and the grammar is said not to be SLR(1). A grammar is said to be SLR(1) if an SLR(1) parser can be built, that is, if there are no conflicts in the parse table.

	[~~TO BE CONTINUED..~~.]		Considering our example grammar, the following parse table would result from applying the steps above:

			[[Image:bupslrtable.png]]

	== Building LALR(1) Parse Tables ==		== Building LALR(1) Parse Tables ==

Root at 18:02, 16 April 2012

2012-04-16T18:02:17Z

← Older revision		Revision as of 18:02, 16 April 2012
Line 133:		Line 133:
	[TO BE CONTINUED...]		[TO BE CONTINUED...]

	==~~= Compacting~~ Parse Tables ===		== Building LALR(1) Parse Tables ==

	== ~~Building LALR(1)~~ Parse Tables ==		== Compacting Parse Tables ==

	== Examples and Exercises ==		== Examples and Exercises ==

Root: /* Building the DFA */

2012-04-16T17:11:34Z

Building the DFA

← Older revision		Revision as of 17:11, 16 April 2012
Line 110:		Line 110:
	[[Image:dfaslr.png\|640px]]		[[Image:dfaslr.png\|640px]]

	~~(a transition is missing, from state 8 to state 6, on +)~~		The items above the red line correspond to kernels, i.e., the items that, in each state, characterize the state, since they are not derivable from any other items in the same state.

	The red ~~items~~ correspond to kernels, i.e., the items that, in each state, characterize the state, since they are not derivable from any other items in the same state.

	State 1 is the accepting state.		State 1 is the accepting state.

← Older revision		Revision as of 13:47, 21 April 2016
Line 153:		Line 153:
	* [[Bottom-Up Parsing/Example 3: SLR(1)\|Example 3: SLR(1)]]		* [[Bottom-Up Parsing/Example 3: SLR(1)\|Example 3: SLR(1)]]
	* [[Bottom-Up Parsing/Example 4: LALR(1)\|Example 4: LALR(1)]]		* [[Bottom-Up Parsing/Example 4: LALR(1)\|Example 4: LALR(1)]]
	* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)		<!--* [[LALR(1) Exercises]] -- with solutions for all exercises (including evaluation exercises)-->
	* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06		* [[Bottom-Up Parsing/Example 5: LALR(1)\|Example 5: LALR(1)]] - appeared in Test 2, 2012/06/06
	* [[Bottom-Up Parsing/Exercise 6: LALR(1)\|Example 6: LALR(1)]] - appeared in Test 2, 2015/06/19		* [[Bottom-Up Parsing/Exercise 6: LALR(1)\|Example 6: LALR(1)]] - appeared in Test 2, 2015/06/19
	* [[Bottom-Up Parsing/Exercise 7: LALR(1)\|Example 7: LALR(1)]] - appeared in Test 2, 2015/06/19		* [[Bottom-Up Parsing/Exercise 7: LALR(1)\|Example 7: LALR(1)]] - appeared in Test 2, 2015/06/19
			* [[Bottom-Up Parsing/Exercise 8: LALR(1)\|Exercise 8: LALR(1)]] - '''S -> G b b''' etc.
			* [[Bottom-Up Parsing/Exercise 9: LALR(1)\|Exercise 9: LALR(1)]] - '''E -> [ E ; L ]''' etc.
			* [[Bottom-Up Parsing/Exercise 10: LALR(1)\|Exercise 10: LALR(1)]] - '''S -> i S''' etc.
			* [[Bottom-Up Parsing/Exercise 11: LALR(1)\|Exercise 11: LALR(1)]] - '''A -> B y y''' etc.
			* [[Bottom-Up Parsing/Exercise 12: LALR(1)\|Exercise 12: LALR(1)]] - '''A -> B x y''' etc.
			* [[Bottom-Up Parsing/Exercise 13: LALR(1)\|Exercise 13: LALR(1)]] - '''A -> A B A x''' etc.