Context-free formal grammar
Incomputer science , asimple precedence grammar is acontext-free formal grammar that can be parsed with asimple precedence parser .[ 1] Claude Pair ,[ 2] Robert Floyd , byNiklaus Wirth andHelmut Weber who published a paper, entitledEULER: a generalization of ALGOL, and its formal definition , published in 1966 in theCommunications of the ACM .[ 3]
G = (N , Σ,P ,S ) is a simple precedence grammar if all the production rules inP comply with the following constraints:
S → a S S b | c {\displaystyle S\to aSSb|c} precedence table S a b c $ S = ˙ ⋖ = ˙ ⋖ a = ˙ ⋖ ⋖ b ⋗ ⋗ ⋗ c ⋗ ⋗ ⋗ ⋗ $ ⋖ ⋖ {\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&{\dot {=}}&\lessdot &{\dot {=}}&\lessdot &\\a&{\dot {=}}&\lessdot &&\lessdot &\\b&&\gtrdot &&\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}} Simple precedence parser [ edit ] Asimple precedence parser is a type ofbottom-up parser forcontext-free grammars that can be used only bysimple precedence grammars .
The implementation of the parser is quite similar to the genericbottom-up parser . A stack is used to store aviable prefix of asentential form from arightmost derivation . The symbols ⋖, ≐ and ⋗ are used to identify thepivot , and to know when toShift or when toReduce .
Compute theWirth–Weber precedence relationship table for a grammar with initial symbol S. Initialize a stack with thestarting marker $. Append anending marker $ to the string being parsed (Input ). Until Stack equals "$ S" and Input equals "$"Search the table for the relationship between Top(stack) and NextToken(Input) if the relationship is ⋖ or ≐Shift :Push(Stack, relationship) Push(Stack, NextToken(Input)) RemoveNextToken(Input) if the relationship is ⋗Reduce :SearchProductionToReduce(Stack) Remove the Pivot from the Stack Search the table for the relationship between the nonterminal from the production and first symbol in the stack (Starting from top) Push(Stack, relationship) Push(Stack, Non terminal) SearchProductionToReduce (Stack)
Find the topmost ⋖ in the stack; this and all the symbols above it are thePivot . Find the production of the grammar which has thePivot as its right side. Given following language, which can parse arithmetic expressions with the multiplication and addition operations:
E --> E + T' | T'T' --> TT --> T * F | FF --> ( E' ) | numE' --> E num is a terminal, and thelexer parse any integer asnum ;E represents an arithmetic expression,T is a term andF is a factor.
and the Parsing table:
E E' T T' F + * ( ) num $ E ≐ ⋗ E' ≐ T ⋗ ≐ ⋗ ⋗ T' ⋗ ⋗ ⋗ F ⋗ ⋗ ⋗ ⋗ + ⋖ ≐ ⋖ ⋖ ⋖ * ≐ ⋖ ⋖ ( ⋖ ≐ ⋖ ⋖ ⋖ ⋖ ⋖ ) ⋗ ⋗ ⋗ ⋗ num ⋗ ⋗ ⋗ ⋗ $ ⋖ ⋖ ⋖ ⋖ ⋖ ⋖
STACK PRECEDENCE INPUT ACTION $ ⋖ 2 * ( 1 + 3 )$ SHIFT $ ⋖ 2 ⋗ * ( 1 + 3 )$ REDUCE (F -> num) $ ⋖ F ⋗ * ( 1 + 3 )$ REDUCE (T -> F) $ ⋖ T ≐ * ( 1 + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( 1 + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ 1 + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ 1 ⋗ + 3 )$ REDUCE 4× (F -> num) (T -> F) (T' -> T) (E ->T ') $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ⋖ 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3 ⋗ )$ REDUCE 3× (F -> num) (T -> F) (T' -> T) $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T ⋗ )$ REDUCE 2× (E -> E + T) (E' -> E) $ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )$ SHIFT $ ⋖ T ≐ * ⋖ ( ≐ E' ≐ ) ⋗ $ REDUCE (F -> ( E' )) $ ⋖ T ≐ * ≐ F ⋗ $ REDUCE (T -> T * F) $ ⋖ T ⋗ $ REDUCE 2× (T' -> T) (E -> T') $ ⋖ E $ ACCEPT
[ edit ] Incomputer science , aWirth–Weber relationship between a pair of symbols( V t ∪ V n ) {\displaystyle (V_{t}\cup V_{n})} formal grammar is asimple precedence grammar . In such a case, thesimple precedence parser can be used. The relationship is named after computer scientistsNiklaus Wirth and Helmut Weber.
The goal is to identify when the viable prefixes have thepivot and must be reduced. A⋗ {\displaystyle \gtrdot } pivot is found, a⋖ {\displaystyle \lessdot } pivot is starting, and a≐ {\displaystyle \doteq } pivot .
G = ⟨ V n , V t , S , P ⟩ {\displaystyle G=\langle V_{n},V_{t},S,P\rangle } X ≐ Y ⟺ { A → α X Y β ∈ P A ∈ V n α , β ∈ ( V n ∪ V t ) ∗ X , Y ∈ ( V n ∪ V t ) X ⋖ Y ⟺ { A → α X B β ∈ P B ⇒ + Y γ A , B ∈ V n α , β , γ ∈ ( V n ∪ V t ) ∗ X , Y ∈ ( V n ∪ V t ) X ⋗ Y ⟺ { A → α B Y β ∈ P B ⇒ + γ X Y ⇒ ∗ a δ A , B ∈ V n α , β , γ , δ ∈ ( V n ∪ V t ) ∗ X , Y ∈ ( V n ∪ V t ) a ∈ V t {\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}} Precedence relations computing algorithm [ edit ] We will define three sets for a symbol:
H e a d + ( X ) = { Y ∣ X ⇒ + Y α } T a i l + ( X ) = { Y ∣ X ⇒ + α Y } H e a d ∗ ( X ) = ( H e a d + ( X ) ∪ { X } ) ∩ V t {\displaystyle {\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}} Head* (X ) isX ifX is a terminal, and ifX is a non-terminal, Head* (X ) is the set with only the terminals belonging to Head+ (X ). This set is equivalent toFirst-set orFi(X ) described inLL parser . Head+ (X ) and Tail+ (X ) are ∅ ifX is a terminal. The pseudocode for computing relations is:
⋖ {\displaystyle \lessdot } ⋗ {\displaystyle \gtrdot } cartesian product between the sets/elements.S → a S S b | c {\displaystyle S\to aSSb|c}
Head+ (a ) = ∅ Head+ (S ) = {a, c } Head+ (b ) = ∅ Head+ (c ) = ∅ Tail+ (a ) = ∅ Tail+ (S ) = {b, c } Tail+ (b ) = ∅ Tail+ (c ) = ∅ Head* (a ) =a Head* (S ) = {a, c } Head* (b ) =b Head* (c ) =c S → a S S b {\displaystyle S\to aSSb} a Next toS S Next toS S Next tob S → c {\displaystyle S\to c} there is only one symbol, so no relation is added. precedence table S a b c $ S ≐ ⋖ ≐ ⋖ a ≐ ⋖ ⋖ b ⋗ ⋗ ⋗ ⋗ c ⋗ ⋗ ⋗ ⋗ $ ⋖ ⋖ {\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}} S → a | a T | [ S ] {\displaystyle S\to a|aT|[S]}
T → b | b T {\displaystyle T\to b|bT}
Head+ (S ) = {a, [ } Head+ (a ) = ∅ Head+ (T ) = {b } Head+ ([ ) = ∅ Head+ (] ) = ∅ Head+ (b ) = ∅ Tail+ (S ) = {a, T, ], b } Tail+ (a ) = ∅ Tail+ (T ) = {b, T } Tail+ ([ ) = ∅ Tail+ (] ) = ∅ Tail+ (b ) = ∅ Head* (S ) = {a, [ } Head* (a ) =a Head* (T ) = {b } Head* ([ ) =[ Head* (] ) =] Head* (b ) =b precedence table S T a b [ ] $ S ≐ ≐ T ⋗ ⋗ a ≐ ⋖ ⋗ ⋗ b ≐ ⋖ ⋗ ⋗ [ ≐ ⋖ ⋖ ] ⋗ ⋗ $ ≐ ⋖ ⋖ {\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}} ^ The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972. ^ Claude Pair (1964). "Arbres, piles et compilation".Revue française de traitement de l'information . Trees, stacks and compiling ^ Machines, Languages, and Computation Prentice–Hall , 1978,ISBN 9780135422588 Wirth and Weber [1966] generalized Floyd's precedence grammars, obtaining the simple precedence grammars. Alfred V. Aho, Jeffrey D. Ullman (1977).Principles of Compiler Design . 1st Edition. Addison–Wesley. William A. Barrett, John D. Couch (1979).Compiler construction: Theory and Practice . Science Research Associate. Jean-Paul Tremblay, P. G. Sorenson (1985).The Theory and Practice of Compiler Writing . McGraw–Hill. Aho, Alfred V.; Ullman, Jeffrey D.,The theory of parsing, translation, and compiling
