Attribute Grammars - Revision history

Root: /* Attribute Types and Parser Actions */

2026-04-29T09:05:48Z

Attribute Types and Parser Actions

← Older revision		Revision as of 09:05, 29 April 2026
Line 16:		Line 16:
	* S-Attributed Grammars: In these grammars, attribute values are only synthesized; that is, they depend only on the attribute values of their children. This makes S-attributed grammars simpler and often easier to manage. S-attributed grammars are well-suited to "bottom-up" or "rightmost" parsing methods, like LR parsing, where nodes corresponding to the right-hand side of a production are created before the node for the left-hand side.		* S-Attributed Grammars: In these grammars, attribute values are only synthesized; that is, they depend only on the attribute values of their children. This makes S-attributed grammars simpler and often easier to manage. S-attributed grammars are well-suited to "bottom-up" or "rightmost" parsing methods, like LR parsing, where nodes corresponding to the right-hand side of a production are created before the node for the left-hand side.
	* L-Attributed Grammars: These grammars allow attributes to be inherited as well as synthesized, but with a restriction: an attribute can only inherit from the left, meaning that inherited attributes are dependent on either the attributes of the parent node, or the attributes of siblings to the left (i.e., previously processed siblings). This restriction makes L-attributed grammars suitable for "left-to-right" parsing methods. Both top-down (like LL parsing) and bottom-up parsers (with some restrictions) can handle L-attributed grammars.		* L-Attributed Grammars: These grammars allow attributes to be inherited as well as synthesized, but with a restriction: an attribute can only inherit from the left, meaning that inherited attributes are dependent on either the attributes of the parent node, or the attributes of siblings to the left (i.e., previously processed siblings). This restriction makes L-attributed grammars suitable for "left-to-right" parsing methods. Both top-down (like LL parsing) and bottom-up parsers (with some restrictions) can handle L-attributed grammars.

			== Videos ==
			* Part 1: Attribute Grammars: https://www.youtube.com/watch?v=eb1KP-RoMyY
			* Part 2: Attribute Grammars: https://www.youtube.com/watch?v=WQviJgOj3ac
			* Part 3: Attribute grammars and YACC/Bison: https://www.youtube.com/watch?v=1Mu-n34-kvw

	== Exercises ==		== Exercises ==

Root at 07:18, 18 May 2023

2023-05-18T07:18:12Z

← Older revision		Revision as of 07:18, 18 May 2023
Line 1:		Line 1:
	{{NAVCompiladores}}		{{NAVCompiladores}}
	~~Topics: attributes in grammar symbols; syntax-directed evaluation.~~

	~~Synthesized attributes: passed from child nodes to parent nodes.~~		== Attribute Grammars ==

	~~Inherited~~ attributes: may be ~~passed from parent- to child nodes or between siblings~~.		Attributes in grammar symbols form a fundamental concept in compiler design, especially in semantic analysis. Attributes provide a way to associate information with each grammar symbol. This information is used to store properties of language constructs like the datatype, number of digits in a number, the value of a constant, etc. When the parser recognizes a language construct represented by a grammar symbol, it uses the attribute values to build other attributes or the abstract syntax tree. These attributes may be used later in the symbol table.

	S-~~attributed grammars: only synthesized~~ attributes.		During analysis, the parser computes the values of the attributes. This is called syntax-directed evaluation and provides a simple form of semantics. Syntax-directed translates a sequence of input symbols (such as a source program) into an output sequence (such as object code) by means of a syntax-directed translator (often integrated with the parsing process). This method is based on the grammar and its added semantic rules, linking the grammar productions with actions to be performed when these productions are used during parsing. The semantic rules can access and manipulate the attributes of grammar symbols.

	L-~~attributed~~ grammars: inherited attributes are ~~only~~ dependent on the ~~parents'~~ attributes or on the ~~older~~ siblings' (i.e., ~~when evaluating~~ left-to-right~~, only previously seen attributes are needed~~).		The attributes are usually divided into two groups, according with their dependencies on the parse tree:
			* Synthesized Attributes: These attributes are calculated from attribute values of the child nodes. Their value depends only on the values in the children of their node. For example, in a grammar representing arithmetic expressions, the value of an expression could be a synthesized attribute computed from the values of its sub-expressions.
			* Inherited Attributes: These attributes get their values from the parent node and/or from their siblings. Their value depends on the nodes' parent and/or siblings in the parse tree. For example, in a language where variables must be declared before use, an attribute of a variable-use node could be inherited from an ancestor node where the variable was declared.

			== Attribute Types and Parser Actions ==

			Depending on the type of parser (frequently, top-down or bottom-up), and the type of attribute, attribute computation may occur in specific ways for each grammar type:
			* S-Attributed Grammars: In these grammars, attribute values are only synthesized; that is, they depend only on the attribute values of their children. This makes S-attributed grammars simpler and often easier to manage. S-attributed grammars are well-suited to "bottom-up" or "rightmost" parsing methods, like LR parsing, where nodes corresponding to the right-hand side of a production are created before the node for the left-hand side.
			* L-Attributed Grammars: These grammars allow attributes to be inherited as well as synthesized, but with a restriction: an attribute can only inherit from the left, meaning that inherited attributes are dependent on either the attributes of the parent node, or the attributes of siblings to the left (i.e., previously processed siblings). This restriction makes L-attributed grammars suitable for "left-to-right" parsing methods. Both top-down (like LL parsing) and bottom-up parsers (with some restrictions) can handle L-attributed grammars.

	== Exercises ==		== Exercises ==

Root: /* Exercises */

2018-07-03T12:07:23Z

Exercises

← Older revision		Revision as of 12:07, 3 July 2018
Line 24:		Line 24:
	* [[Attribute Grammars/Exercise 11: Operadores Lógicos\|Exercise 11: Operadores Lógicos]] (Teste 2, 2014/2015)		* [[Attribute Grammars/Exercise 11: Operadores Lógicos\|Exercise 11: Operadores Lógicos]] (Teste 2, 2014/2015)
	* [[Attribute Grammars/Exercise 12: Operadores Lógicos\|Exercise 12: Operadores Lógicos]] (Teste 2, 2014/2015)		* [[Attribute Grammars/Exercise 12: Operadores Lógicos\|Exercise 12: Operadores Lógicos]] (Teste 2, 2014/2015)
			* [[Attribute Grammars/Exercise 13: Operadores Lógicos\|Exercise 13: Operações com números]] (Teste 2, 2017/2018)
			* [[Attribute Grammars/Exercise 14: Operadores Lógicos\|Exercise 14: Operações com números]] (Teste 2, 2017/2018)

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

Root: /* Exercises */

2017-03-29T16:46:48Z

Exercises

← Older revision		Revision as of 16:46, 29 March 2017
Line 17:		Line 17:
	* [[Attribute Grammars/Exercise 4: Expressions with bases (1)\|Exercise 4: Expressions with bases (1)]]		* [[Attribute Grammars/Exercise 4: Expressions with bases (1)\|Exercise 4: Expressions with bases (1)]]
	* [[Attribute Grammars/Exercise 5: Expressions with bases (2)\|Exercise 5: Expressions with bases (2)]]		* [[Attribute Grammars/Exercise 5: Expressions with bases (2)\|Exercise 5: Expressions with bases (2)]]
	* [[Attribute Grammars/Exercise 6: Expressions with bases percentages\|Exercise 5: Expressions with percentages]]		* [[Attribute Grammars/Exercise 6: Expressions with bases percentages\|Exercise 6: Expressions with percentages]]
	* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)		* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)
	* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)		* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)

Root: /* Exercises */

2015-06-22T17:53:04Z

Exercises

← Older revision		Revision as of 17:53, 22 June 2015
Line 22:		Line 22:
	* [[Attribute Grammars/Exercise 9: Text relevance\|Exercise 9: Text relevance]] (Teste 2, 2011/2012)		* [[Attribute Grammars/Exercise 9: Text relevance\|Exercise 9: Text relevance]] (Teste 2, 2011/2012)
	* [[Attribute Grammars/Exercise 10: Expressions and bases\|Exercise 10: Expressions and bases]]		* [[Attribute Grammars/Exercise 10: Expressions and bases\|Exercise 10: Expressions and bases]]
			* [[Attribute Grammars/Exercise 11: Operadores Lógicos\|Exercise 11: Operadores Lógicos]] (Teste 2, 2014/2015)
			* [[Attribute Grammars/Exercise 12: Operadores Lógicos\|Exercise 12: Operadores Lógicos]] (Teste 2, 2014/2015)

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

Root at 14:24, 6 April 2015

2015-04-06T14:24:36Z

← Older revision		Revision as of 14:24, 6 April 2015
Line 23:		Line 23:
	* [[Attribute Grammars/Exercise 10: Expressions and bases\|Exercise 10: Expressions and bases]]		* [[Attribute Grammars/Exercise 10: Expressions and bases\|Exercise 10: Expressions and bases]]

	[[category:~~Compilers~~]]		[[category:Compiladores]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root at 13:34, 3 April 2014

2014-04-03T13:34:32Z

← Older revision		Revision as of 13:34, 3 April 2014
Line 21:		Line 21:
	* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)		* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)
	* [[Attribute Grammars/Exercise 9: Text relevance\|Exercise 9: Text relevance]] (Teste 2, 2011/2012)		* [[Attribute Grammars/Exercise 9: Text relevance\|Exercise 9: Text relevance]] (Teste 2, 2011/2012)
			* [[Attribute Grammars/Exercise 10: Expressions and bases\|Exercise 10: Expressions and bases]]

	[[category:Compilers]]		[[category:Compilers]]
	[[category:Teaching]]		[[category:Teaching]]

Root: /* Exercises */

2012-06-05T13:08:52Z

Exercises

← Older revision		Revision as of 13:08, 5 June 2012
Line 20:		Line 20:
	* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)		* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)
	* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)		* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)
			* [[Attribute Grammars/Exercise 9: Text relevance\|Exercise 9: Text relevance]] (Teste 2, 2011/2012)

	[[category:Compilers]]		[[category:Compilers]]
	[[category:Teaching]]		[[category:Teaching]]

Root at 15:47, 15 June 2011

2011-06-15T15:47:50Z

← Older revision		Revision as of 15:47, 15 June 2011
Line 19:		Line 19:
	* [[Attribute Grammars/Exercise 6: Expressions with bases percentages\|Exercise 5: Expressions with percentages]]		* [[Attribute Grammars/Exercise 6: Expressions with bases percentages\|Exercise 5: Expressions with percentages]]
	* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)		* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)
			* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)

	[[category:Compilers]]		[[category:Compilers]]
	[[category:Teaching]]		[[category:Teaching]]

Root at 17:37, 26 June 2010

2010-06-26T17:37:58Z

← Older revision		Revision as of 17:37, 26 June 2010
Line 1:		Line 1:
			{{NAVCompiladores}}
	Topics: attributes in grammar symbols; syntax-directed evaluation.		Topics: attributes in grammar symbols; syntax-directed evaluation.

← Older revision		Revision as of 16:46, 29 March 2017
Line 17:		Line 17:
	* [[Attribute Grammars/Exercise 4: Expressions with bases (1)\|Exercise 4: Expressions with bases (1)]]		* [[Attribute Grammars/Exercise 4: Expressions with bases (1)\|Exercise 4: Expressions with bases (1)]]
	* [[Attribute Grammars/Exercise 5: Expressions with bases (2)\|Exercise 5: Expressions with bases (2)]]		* [[Attribute Grammars/Exercise 5: Expressions with bases (2)\|Exercise 5: Expressions with bases (2)]]
	* [[Attribute Grammars/Exercise 6: Expressions with bases percentages\|Exercise 5: Expressions with percentages]]		* [[Attribute Grammars/Exercise 6: Expressions with bases percentages\|Exercise 6: Expressions with percentages]]
	* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)		* [[Attribute Grammars/Exercise 7: Lines, characters, and CRCs\|Exercise 7: Lines, characters, and CRCs]] (Teste 2, 2009/2010)
	* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)		* [[Attribute Grammars/Exercise 8: Arithmetic\|Exercise 8: Arithmetic]] (Teste 2, 2010/2011)