A feladat:

Van-e egyszerű precedencia elemző az alábbi nyelvtanokhoz? Ha van, akkor azt is nézzük meg, hogy erős-e avagy gyenge.
(a) $S\ensuremath{\rightarrow} SA\;\vert A$ , $A\ensuremath{\rightarrow} (S)\;\vert\;()$
(b) $S\ensuremath{\rightarrow} $ if E then S else $S\;\vert\;a$ , $E\ensuremath{\rightarrow} E$ or $b\;\vert\;b$
(c) $S\ensuremath{\rightarrow} A;A$ , $A\ensuremath{\rightarrow} [S]\;\vert\;[i]\;\vert\;i$

A megoldás:

(a)


  S A ( ) $\epsilon$
S   \ensuremath{\dot{=}} \ensuremath{<\cdot} \ensuremath{\dot{=}}  
A     \ensuremath{\cdot>} \ensuremath{\cdot>} \ensuremath{\cdot>}
( \ensuremath{<\cdot}, \ensuremath{\dot{=}} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{\dot{=}}  
)     \ensuremath{\cdot>} \ensuremath{\cdot>} \ensuremath{\cdot>}
$\epsilon$ \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot}    



Mivel csak a nyél eleje meg a nyél közepe relációk ütköznek, azért még van esély, hogy egyszerű precedencia nyelvtan legyen, de csak akkor, ha a problémás helyzet, azaz az (-S pár esetén mindig feloldható, hogy nyél eleje van vagy nyél közepe. Itt most ez a helyzet, azaz mindig el lehet dönteni, hogy melyikről van szó: ha az S-et A követi, akkor a nyél eleje, ha ), akkor a nyél közepe reláció az érvényes.


Lássuk egy példán, hogy hogyan megy:


$(\epsilon, ()(()), \epsilon)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} (, )(()), \epsilon)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} (\ensuremath{\dot{=}} ), (()), \epsilon)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} A, (()), 4)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S, (()), 42)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S\ensuremath{<\cdot} (, ()), 42)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S\ensuremath{<\cdot} (\ensuremath{<\cdot} (, )), 42)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S\ensuremath{<\cdot} (\ensuremath{<\cdot} (\ensuremath{\dot{=}} ), ), 42)\ensuremath{\rightarrow} $
$ (\ensuremath{<\cdot} S\ensuremath{<\cdot} (\ensuremath{<\cdot} A, ), 424)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S\ensuremath{<\cdot} (\ensuremath{<\cdot} ,\ensuremath{\dot{=}} S, ), 4242)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S\ensuremath{<\cdot} (\ensuremath{<\cdot} ,\ensuremath{\dot{=}} S\ensuremath{\dot{=}} ), \epsilon, 4242)\ensuremath{\rightarrow} $
$(\ensuremath{<\cdot} S\ensuremath{\dot{=}} A, \epsilon, 42423)\ensuremath{\rightarrow} $
$(S, \epsilon, 424231)\ensuremath{\rightarrow} $Accept.


Itt a problémás helyzet úgy oldódott fel, hogy az alternatív nyélként kínálkozó S) nem jobboldal sehol.

(b)

  if then else S E a b or $\epsilon$
if         \ensuremath{\dot{=}}, \ensuremath{<\cdot}   \ensuremath{<\cdot}    
then \ensuremath{<\cdot}     \ensuremath{\dot{=}}   \ensuremath{<\cdot}      
else \ensuremath{<\cdot}     \ensuremath{\dot{=}}   \ensuremath{<\cdot}      
S     \ensuremath{\cdot>}, \ensuremath{\dot{=}}           \ensuremath{\cdot>}
E   \ensuremath{\dot{=}} \ensuremath{<\cdot}         \ensuremath{\dot{=}}  
a     \ensuremath{\cdot>}           \ensuremath{\cdot>}
b   \ensuremath{\cdot>}           \ensuremath{\cdot>}  
or             \ensuremath{\dot{=}}    
$\epsilon$ \ensuremath{<\cdot}         \ensuremath{<\cdot}      


Tehát erre nincsen egyszerű precedencia-elemző, lásd az S-else párt.


(c)


  S A ; [ ] i $\epsilon$
S         \ensuremath{\dot{=}}    
A     \ensuremath{\dot{=}}   \ensuremath{\cdot>}   \ensuremath{\cdot>}
;   \ensuremath{\dot{=}}   \ensuremath{<\cdot}   \ensuremath{<\cdot}  
[ \ensuremath{\dot{=}} \ensuremath{<\cdot}   \ensuremath{<\cdot}   \ensuremath{<\cdot}, \ensuremath{\dot{=}}  
]     \ensuremath{\cdot>}   \ensuremath{\cdot>}   \ensuremath{\cdot>}
i     \ensuremath{\cdot>}   \ensuremath{\dot{=}}, \ensuremath{\cdot>}   \ensuremath{\cdot>}
$\epsilon$   \ensuremath{<\cdot}   \ensuremath{<\cdot}   \ensuremath{<\cdot}  



Tehát erre sincsen egyszerű precedencia-elemző, lásd az i-] párt.