Introduction to Syntax - Revision history

Root at 19:02, 26 April 2026

2026-04-26T19:02:35Z

← Older revision		Revision as of 19:02, 26 April 2026
Line 10:		Line 10:
	* Direct derivation: <math>u\underset{G}{\Rightarrow}v\;\text{iff}\;\exists_{w_1,w_2\in{}V^*}: \exists_{(u',v')\in{}R}: u=w_1u'w_2 \wedge v=w_1v'w_2</math>		* Direct derivation: <math>u\underset{G}{\Rightarrow}v\;\text{iff}\;\exists_{w_1,w_2\in{}V^*}: \exists_{(u',v')\in{}R}: u=w_1u'w_2 \wedge v=w_1v'w_2</math>
	* Derivation: <math>w_0\underset{G}{\Rightarrow}w_1\underset{G}{\Rightarrow}\cdots\underset{G}{\Rightarrow}w_n\;\Leftrightarrow{}w_0\overset{*}{\underset{G}{\Rightarrow}}w_n</math>		* Derivation: <math>w_0\underset{G}{\Rightarrow}w_1\underset{G}{\Rightarrow}\cdots\underset{G}{\Rightarrow}w_n\;\Leftrightarrow{}w_0\overset{*}{\underset{G}{\Rightarrow}}w_n</math>
	* Generated language: <math>L(G) = \{ w\~~: \|\:~~ w \in \Sigma^* \~~wedge{}~~S\~~overset~~{*}{\~~underset~~{G}{\Rightarrow}}w \}</math>		* Generated language: <math>L(G) = \{ w \mid w \in \Sigma^* \land S \underset{G}{\overset{*}{\Rightarrow}} w \}</math>

	== Context-free Grammars ==		== Context-free Grammars ==

Root at 21:46, 3 December 2018

2018-12-03T21:46:09Z

Root: /* What is a Grammar? */

2018-12-03T21:42:33Z

What is a Grammar?

← Older revision		Revision as of 21:42, 3 December 2018
Line 4:		Line 4:
	= What is a Grammar? =		= What is a Grammar? =

	An unrestricted grammar is a quadruple <~~amsmath~~>G=(V,\Sigma,R,S)</~~amsmath~~>, where <~~amsmath~~>V</~~amsmath~~> is an alphabet; <~~amsmath~~>\Sigma</~~amsmath~~> is the set of terminal symbols (<~~amsmath~~>\Sigma\subseteq{}V</~~amsmath~~>); <~~amsmath~~>(V-\Sigma)</~~amsmath~~> is the set of non-terminal symbols; <~~amsmath~~>S</~~amsmath~~> is the initial symbol; and <~~amsmath~~>R</~~amsmath~~> is a set of rules (a finite subset of <~~amsmath~~>(V^(V-\Sigma)V^)\times{}V^*</~~amsmath~~>).		An unrestricted grammar is a quadruple <math>G=(V,\Sigma,R,S)</math>, where <math>V</math> is an alphabet; <math>\Sigma</math> is the set of terminal symbols (<math>\Sigma\subseteq{}V</math>); <math>(V-\Sigma)</math> is the set of non-terminal symbols; <math>S</math> is the initial symbol; and <math>R</math> is a set of rules (a finite subset of <math>(V^(V-\Sigma)V^)\times{}V^*</math>).

	The following are defined:		The following are defined:

	* Direct derivation: <~~amsmath~~>u\underset{~~\text{\tiny~~ G}}{\Rightarrow}v\;\text{iff}\;\exists_{w_1,w_2\in{}V^*}: \exists_{(u',v')\in{}R}: u=w_1u'w_2 \wedge v=w_1v'w_2</~~amsmath~~>		* Direct derivation: <math>u\underset{G}{\Rightarrow}v\;\text{iff}\;\exists_{w_1,w_2\in{}V^*}: \exists_{(u',v')\in{}R}: u=w_1u'w_2 \wedge v=w_1v'w_2</math>
	* Derivation: <~~amsmath~~>w_0\underset{~~\text{\tiny~~ G}}{\Rightarrow}w_1\underset{~~\text{\tiny~~ G}}{\Rightarrow}\cdots\underset{~~\text{\tiny~~ G}}{\Rightarrow}w_n\;\Leftrightarrow{}w_0\overset{*}{\underset{~~\text{\tiny~~ G}}{\Rightarrow}}w_n</~~amsmath~~>		* Derivation: <math>w_0\underset{G}{\Rightarrow}w_1\underset{G}{\Rightarrow}\cdots\underset{G}{\Rightarrow}w_n\;\Leftrightarrow{}w_0\overset{*}{\underset{G}{\Rightarrow}}w_n</math>
	* Generated language: <~~amsmath~~>L(G) = \{ w\: \|\: w \in \Sigma^* \wedge{}S\overset{*}{\underset{~~\text{\tiny~~ G}}{\Rightarrow}}w \}</~~amsmath~~>		* Generated language: <math>L(G) = \{ w\: \|\: w \in \Sigma^* \wedge{}S\overset{*}{\underset{G}{\Rightarrow}}w \}</math>

	== Context-free Grammars ==		== Context-free Grammars ==
Line 16:		Line 16:
	The above grammar is unrestricted in its derivation capabilities and directly supports context-dependent rules.		The above grammar is unrestricted in its derivation capabilities and directly supports context-dependent rules.

	In our study of programming language processing, though, only context-free grammars will be considered. This means that the <~~amsmath~~>R</~~amsmath~~> set is defined on <~~amsmath~~>(V-\Sigma)\times{}V^*</~~amsmath~~>, i.e., only non-terminals are allowed on the left side of a rule.		In our study of programming language processing, though, only context-free grammars will be considered. This means that the <math>R</math> set is defined on <math>(V-\Sigma)\times{}V^*</math>, i.e., only non-terminals are allowed on the left side of a rule.

	Even though we gave a formal definition of grammar, seldom will we use them described in that form. Most grammars are described in [[wikipedia:Backus–Naur Form\|Backus-Naur Form]] (BNF), [[wikipedia:Extended Backus–Naur Form\|Extended Backus–Naur Form]] (EBNF), or other [[wikipedia:metasyntax\|metasyntax]].		Even though we gave a formal definition of grammar, seldom will we use them described in that form. Most grammars are described in [[wikipedia:Backus–Naur Form\|Backus-Naur Form]] (BNF), [[wikipedia:Extended Backus–Naur Form\|Extended Backus–Naur Form]] (EBNF), or other [[wikipedia:metasyntax\|metasyntax]].

Root: /* Context-free Grammars */

2016-06-30T10:29:06Z

Context-free Grammars

← Older revision		Revision as of 10:29, 30 June 2016
Line 18:		Line 18:
	In our study of programming language processing, though, only context-free grammars will be considered. This means that the <amsmath>R</amsmath> set is defined on <amsmath>(V-\Sigma)\times{}V^*</amsmath>, i.e., only non-terminals are allowed on the left side of a rule.		In our study of programming language processing, though, only context-free grammars will be considered. This means that the <amsmath>R</amsmath> set is defined on <amsmath>(V-\Sigma)\times{}V^*</amsmath>, i.e., only non-terminals are allowed on the left side of a rule.

	Even though we gave a formal definition of grammar, seldom will we use them described in that form. Most grammars are described in [[wikipedia:~~Bakus-Naur~~ Form\|~~Bakus~~-Naur Form]] (BNF), [[wikipedia:Extended Backus–Naur Form\|Extended Backus–Naur Form]] (EBNF), or other [[wikipedia:metasyntax\|metasyntax]].		Even though we gave a formal definition of grammar, seldom will we use them described in that form. Most grammars are described in [[wikipedia:Backus–Naur Form\|Backus-Naur Form]] (BNF), [[wikipedia:Extended Backus–Naur Form\|Extended Backus–Naur Form]] (EBNF), or other [[wikipedia:metasyntax\|metasyntax]].

	Consider the following example grammar:		Consider the following example grammar:

Root at 14:28, 6 April 2015

2015-04-06T14:28:03Z

← Older revision		Revision as of 14:28, 6 April 2015
Line 66:		Line 66:
	* [[Introduction to Syntax/Exercise 1\|Exercise 1]] - simple ambiguous grammar.		* [[Introduction to Syntax/Exercise 1\|Exercise 1]] - simple ambiguous grammar.

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

Root at 18:08, 26 June 2010

2010-06-26T18:08:09Z

← Older revision		Revision as of 18:08, 26 June 2010
Line 1:		Line 1:
			{{NAVCompiladores}}
	{{TOCright}}		{{TOCright}}

Root: /* The FIRST and FOLLOW sets */

2010-04-11T20:58:42Z

The FIRST and FOLLOW sets

← Older revision		Revision as of 20:58, 11 April 2010
Line 54:		Line 54:

	The algorithm should be repeated until the FOLLOW set remains unchanged.		The algorithm should be repeated until the FOLLOW set remains unchanged.

			== LOOKAHEADs ==

			The LOOKAHEAD set is defined for a rule as follows:

			LOOKAHEAD(R -> Body) = FIRST(Body) ∪ FOLLOW(R), when Body <amsmath>\overset{*}{\Rightarrow}</amsmath> ε

	= Exercises =		= Exercises =

Root: /* What is a Grammar? */

2010-04-04T18:26:01Z

What is a Grammar?

← Older revision		Revision as of 18:26, 4 April 2010
Line 25:		Line 25:
	F -> <font color='blue'>'''('''</font> E <font color='blue'>''')'''</font> \| <font color='blue'>'''val'''</font>		F -> <font color='blue'>'''('''</font> E <font color='blue'>''')'''</font> \| <font color='blue'>'''val'''</font>

	This grammar provides a description of the syntax of simple additive and multiplicative expressions. The language will be any expression involving the two operators, sets of ~~parenthesis~~ and values (''val''). Tokens (terminals) are in blue. Token ''val'' represents any number and is a terminal in this grammar: in a compiler implementation this would be recognized at the lexical level.		This grammar provides a description of the syntax of simple additive and multiplicative expressions. The language will be any expression involving the two operators, sets of parentheses and values (''val''). Tokens (terminals) are in blue. Token ''val'' represents any number and is a terminal in this grammar: in a compiler implementation this would be recognized at the lexical level.

	= The FIRST and FOLLOW sets =		= The FIRST and FOLLOW sets =

Root: /* Context-free Grammars */

2010-04-04T18:25:25Z

Context-free Grammars

← Older revision		Revision as of 18:25, 4 April 2010
Line 25:		Line 25:
	F -> <font color='blue'>'''('''</font> E <font color='blue'>''')'''</font> \| <font color='blue'>'''val'''</font>		F -> <font color='blue'>'''('''</font> E <font color='blue'>''')'''</font> \| <font color='blue'>'''val'''</font>

	This grammar provides a description of the syntax of ~~simples~~ additive and multiplicative expressions. The language will be any expression involving the two operators, sets of parenthesis and values (''val''). Tokens (terminals) are in blue. Token ''val'' represents any number and is a terminal in this grammar: in a compiler implementation this would be recognized at the lexical level.		This grammar provides a description of the syntax of simple additive and multiplicative expressions. The language will be any expression involving the two operators, sets of parenthesis and values (''val''). Tokens (terminals) are in blue. Token ''val'' represents any number and is a terminal in this grammar: in a compiler implementation this would be recognized at the lexical level.

	= The FIRST and FOLLOW sets =		= The FIRST and FOLLOW sets =

Root: /* Context-free Grammars */

2010-04-04T17:37:57Z

Context-free Grammars

← Older revision		Revision as of 17:37, 4 April 2010
Line 13:		Line 13:
	== Context-free Grammars ==		== Context-free Grammars ==

	The above grammar is unrestricted in its ~~derivations~~ capabilities and directly supports context-dependent rules.		The above grammar is unrestricted in its derivation capabilities and directly supports context-dependent rules.

	In our study of programming language processing, though, only context-free grammars will be considered. This means that the <amsmath>R</amsmath> set is defined on <amsmath>(V-\Sigma)\times{}V^*</amsmath>, i.e., only non-terminals are allowed on the left side of a rule.		In our study of programming language processing, though, only context-free grammars will be considered. This means that the <amsmath>R</amsmath> set is defined on <amsmath>(V-\Sigma)\times{}V^*</amsmath>, i.e., only non-terminals are allowed on the left side of a rule.

← Older revision		Revision as of 21:46, 3 December 2018
Line 37:		Line 37:
	# If X is a non-terminal symbol and X -> ε is a production then add ε to FIRST(X)		# If X is a non-terminal symbol and X -> ε is a production then add ε to FIRST(X)
	# If X is a non-terminal symbol and X -> Y<sub>1</sub>...Y<sub>n</sub> is a production, then		# If X is a non-terminal symbol and X -> Y<sub>1</sub>...Y<sub>n</sub> is a production, then
	#:a ∈ FIRST(X) if a ∈ FIRST(Y<sub>i</sub>) and ε ∈ FIRST(Y<sub>j</sub>), i>j (i.e., Y<sub>j</sub> <~~amsmath~~>\overset{*}{\Rightarrow}</~~amsmath~~> ε)		#:a ∈ FIRST(X) if a ∈ FIRST(Y<sub>i</sub>) and ε ∈ FIRST(Y<sub>j</sub>), i>j (i.e., Y<sub>j</sub> <math>\overset{*}{\Rightarrow}</math> ε)

	As an example, consider production X -> Y<sub>1</sub>...Y<sub>n</sub>		As an example, consider production X -> Y<sub>1</sub>...Y<sub>n</sub>
	* If Y<sub>1</sub> <~~amsmath~~>\overset{*}{\~~nRightarrow~~}</~~amsmath~~> ε then FIRST(X) = FIRST(Y<sub>1</sub>)		* If Y<sub>1</sub> <math>\overset{*}{\not\Rightarrow}</math> ε then FIRST(X) = FIRST(Y<sub>1</sub>)
	* If Y<sub>1</sub> <~~amsmath~~>\overset{}{\Rightarrow}</~~amsmath~~> ε and Y<sub>2</sub> <~~amsmath~~>\overset{}{\~~nRightarrow~~}</~~amsmath~~> ε then FIRST(X) = FIRST(Y<sub>1</sub>) \ {ε} ∪ FIRST(Y<sub>2</sub>)		* If Y<sub>1</sub> <math>\overset{}{\Rightarrow}</math> ε and Y<sub>2</sub> <math>\overset{}{\not\Rightarrow}</math> ε then FIRST(X) = FIRST(Y<sub>1</sub>) \ {ε} ∪ FIRST(Y<sub>2</sub>)
	* If Y<sub>i</sub> <~~amsmath~~>\overset{*}{\Rightarrow}</~~amsmath~~> ε (∀i) then FIRST(X) = ∪<sub>i</sub>(FIRST(Y<sub>i</sub>)\{ε}) ∪ {ε}		* If Y<sub>i</sub> <math>\overset{*}{\Rightarrow}</math> ε (∀i) then FIRST(X) = ∪<sub>i</sub>(FIRST(Y<sub>i</sub>)\{ε}) ∪ {ε}

	The FIRST set can also be computed for a string Y<sub>1</sub>...Y<sub>n</sub> much in the same way as in case 3 above.		The FIRST set can also be computed for a string Y<sub>1</sub>...Y<sub>n</sub> much in the same way as in case 3 above.
Line 52:		Line 52:
	# If X is the grammar's initial symbol then {$} ⊆ FOLLOW(X)		# If X is the grammar's initial symbol then {$} ⊆ FOLLOW(X)
	# If A -> αXβ is a production, then FIRST(β)\{ε} ⊆ FOLLOW(X)		# If A -> αXβ is a production, then FIRST(β)\{ε} ⊆ FOLLOW(X)
	# If A -> αX or A -> αXβ (β <~~amsmath~~>\overset{*}{\Rightarrow}</~~amsmath~~> ε), then FOLLOW(A) ⊆ FOLLOW(X)		# If A -> αX or A -> αXβ (β <math>\overset{*}{\Rightarrow}</math> ε), then FOLLOW(A) ⊆ FOLLOW(X)

	The algorithm should be repeated until the FOLLOW set remains unchanged.		The algorithm should be repeated until the FOLLOW set remains unchanged.
Line 60:		Line 60:
	The LOOKAHEAD set is defined for a rule as follows:		The LOOKAHEAD set is defined for a rule as follows:

	LOOKAHEAD(R -> Body) = FIRST(Body) ∪ FOLLOW(R), when Body <~~amsmath~~>\overset{*}{\Rightarrow}</~~amsmath~~> ε		LOOKAHEAD(R -> Body) = FIRST(Body) ∪ FOLLOW(R), when Body <math>\overset{*}{\Rightarrow}</math> ε

	= Exercises =		= Exercises =