Wirth–Weber precedence relationship
(Learn how and when to remove this message) In computer science, a Wirth–Weber relationship between a pair of symbols
is necessary to determine if a formal grammar is a simple precedence grammar. In such a case, the simple precedence parser can be used. The relationship is named after computer scientists Niklaus Wirth and Helmut Weber.
The goal is to identify when the viable prefixes have the pivot and must be reduced. A
means that the pivot is found, a
means that a potential pivot is starting, and a
means that a relationship remains in the same pivot.
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2be7a27a0a27fa1064a6001f0761005c6b28cd6d)
Precedence relations computing algorithm
We will define three sets for a symbol:
Head*(X) is X if X is a terminal, and if X is a non-terminal, Head*(X) is the set with only the terminals belonging to Head+(X). This set is equivalent to First-set or Fi(X) described in LL parser.
Head+(X) and Tail+(X) are ∅ if X is a terminal.
The pseudocode for computing relations is:
- RelationTable := ∅
- For each production
- For each two adjacent symbols X Y in α
- add(RelationTable,
) - add(RelationTable,
) - add(RelationTable,
)
- add(RelationTable,
) where S is the initial non terminal of the grammar, and $ is a limit marker - add(RelationTable,
) where S is the initial non terminal of the grammar, and $ is a limit marker
and
are used with sets instead of elements as they were defined, in this case you must add all the cartesian product between the sets/elements.
Examples
Example 1
- 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
- a Next to S
![{\displaystyle a\doteq S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d26befcb5272d33fbe6efba8828c7bdb6513558f)
![{\displaystyle a\lessdot a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a87fcc13f097a85618bf123df91b75564ff2ad89)
![{\displaystyle a\lessdot c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a25284b5bb9577600be3b530b19081ad62dd5d2)
- S Next to S
![{\displaystyle S\doteq S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cddbe5aa9d60509aef3b30a1ac5cef0ad4c2141)
![{\displaystyle S\lessdot a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4509e120cb8c81c346c69497c02c7bb0c659f048)
![{\displaystyle S\lessdot c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/daa67c7cdc156869102ba0d2dfd0a39b2f38a7bb)
![{\displaystyle b\gtrdot a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dba2caab3df71bca97af14db896ead979c5650c)
![{\displaystyle b\gtrdot c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d046ff057ddf0e85631f1e20fd8aa7a41611160)
![{\displaystyle c\gtrdot a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e95b87381631164a4b900dfe0d4215d7f94cc996)
![{\displaystyle c\gtrdot c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d5a730aea6ee52fdee265b3fbaff39df4c380ab)
- S Next to b
![{\displaystyle S\doteq b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/325f36da5dc10e324e2d6f3adffc73ac6325f168)
![{\displaystyle b\gtrdot b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5921c2d843655ff8163fbd58dbfbc74a3e014239)
![{\displaystyle c\gtrdot b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba94ca44f72a1817bff63328e416dbbf6b80a11)
- there is only one symbol, so no relation is added.
- precedence table
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8778fc5da10445c0291caf3578fc743a33a36c54)
Example 2
- 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
![{\displaystyle S\to aT}](https://wikimedia.org/api/rest_v1/media/math/render/svg/429605eed020af8de16a615d16e1b9d7ed185a46)
- a Next to T
![{\displaystyle a\doteq T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7762ef00577589384e2ec1cbbf144ce4fc575a9)
![{\displaystyle a\lessdot b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9721c53f2884b2702049a7d4e17b3ade3b21af37)
![{\displaystyle S\to [S]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee50b6958472283dfaa228f8c159ef586681b615)
- [ Next to S
![{\displaystyle [\doteq S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f48c9b621adcf63d1d2229af2f0a721c0cde5c9e)
![{\displaystyle [\lessdot a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cdc6ccb144c9839a177197ec317e8df71079ea5)
![{\displaystyle [\lessdot [}](https://wikimedia.org/api/rest_v1/media/math/render/svg/761af14aac8e3649bfb21f0cae0006b84afc10dc)
- S Next to ]
![{\displaystyle S\doteq ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1284b981412a510b580c3dabfa7590a7bd7922dd)
![{\displaystyle a\gtrdot ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e458d62714aa1d5433e4a0484e435fd2297cc52)
![{\displaystyle T\gtrdot ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52d9a2389ec97bb72f9357583dee6df843fd3714)
![{\displaystyle ]\gtrdot ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cb8652498bffd0605c33be702ff3a091dfa5c68)
![{\displaystyle b\gtrdot ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b35535fcb3f2f5264e57af0ab7977dfd3af0257)
![{\displaystyle T\to bT}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57355907e939d9a50a8e44c2c9282282bdc86821)
- b Next to T
![{\displaystyle b\doteq T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7722cd6535b56fc4f92ba59ca386c0788a5db1a9)
![{\displaystyle b\lessdot b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a245ee7afa3ab5ac21e5caf90ae84affb908df0)
- precedence table
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b964c44c9fa0b977fba266f30211535bcfbed025)
Further reading
- Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling
Niklaus Wirth
Software | Programming languages | Euler (1965) → PL360 (1966) → ALGOL W (1966) → Pascal (1970) → Modula (1975) → Modula-2 (1978) → Object Pascal (1986) → Oberon (1987) → Oberon-2 (1991) → Lola (1995) → Active Oberon (1998) → Oberon-07 (2007) |
---|
Operating systems | Oberon System (1987) → Active Object System (AOS, 2002), Bluebottle (2005), A2 (2008) |
---|
Formalisms | - Wirth's law
- Wirth syntax notation
- Wirth–Weber precedence relationship
|
---|
Books | |
---|
|
---|
Workstations | Lilith (1977) → Ceres (1985) |
---|
Workplaces | |
---|
Collaborators | |
---|
Awards | |
---|
Category |