(→What is a Grammar?) |
(→What is a Grammar?) |
||
Line 3: | Line 3: | ||
= 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>). | |
− | * <amsmath>u\underset{\text{\tiny G}}{\Rightarrow}v\;\text{ | + | The following are defined: |
− | * <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> | + | |
− | * <amsmath>L(G) = \{ w\: |\: w \in \Sigma^* \wedge{}S\overset{*}{\underset{\text{\tiny G}}{\Rightarrow}}w \}</amsmath> | + | * 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> |
+ | * 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> | ||
+ | * Generated language: <amsmath>L(G) = \{ w\: |\: w \in \Sigma^* \wedge{}S\overset{*}{\underset{\text{\tiny G}}{\Rightarrow}}w \}</amsmath> | ||
= The FIRST and FOLLOW sets = | = The FIRST and FOLLOW sets = |
An unrestricted grammar is a quadruple , where is an alphabet; is the set of terminal symbols (); is the set of non-terminal symbols; is the initial symbol; and is a set of rules (a finite subset of ).
The following are defined:
The FIRST set for a given string or symbol can be computed as follows:
As an example, consider production X -> Y1...Yn
The FIRST set can also be computed for a string Y1...Yn much in the same way as in case 3 above.
The FOLLOW set is computed for non-terminals and indicates the set of terminal symbols that are possible after a given non-terminal. The special symbol $ is used to represent the end of phrase (end of input).
The algorithm should be repeated until the FOLLOW set remains unchanged.