HOCHSCHULE
Fachbereich Informatik
Prof. Dr. Christian Wagenknecht
University of Applied Sciences
ZITTAU/GÖRLITZ
Formale Sprachen und Automaten
Übung: LL(k)-Sprachen und LL(1)-Forderungen
Zur Erinnerung:
Definition LL(1)-Forderung 1
Eine kfG G erfüllt die LL(1)-Forderung 1, wenn für jedes Nichtterminal X von G, mit
X → α1 | α2 | . . . | αn und αi ∈ (N ∪ T )∗ , gilt
F IRST (αi ) ∩ F IRST (αj ) = ∅ für alle i 6= j.
Definition Forderung 2
∗
Eine kfG G erfüllt die LL(1)-Forderung 2, wenn für jedes Nichtterminal X, mit X ⇒ ε,
gilt
F IRST (X) ∩ F OLLOW (X) = ∅.
Aufgaben
1. Prüfen Sie für jede Grammatik in den folgenden Aufgaben, ob es eine LL(1)Grammatik ist.
a)
G
N
T
P
=
=
=
=
(N, T, P, s)
{S, X, C, B}
{d, a}
{S → X d
X→B a | C
C→ε
B→d
}
s = S
b)
G
N
T
P
=
=
=
=
(N, T, P, s)
{E, ES, T, T S, F }
{+, *, (, ), a}
{E → T ES
ES → + T ES | ε
T → F TS
TS → * F TS | ε
F →(E ) | a
}
s = E
c)
G
N
T
P
=
=
=
=
(N, T, P, s)
{S, S2}
{if, a, then, s, else}
{S → if a then S2 | s
S2 → S else S | S
}
s = S
d)
G
N
T
P
=
=
=
=
(N, T, P, s)
{S, S2}
{if, a, then, s, else}
{S → if a then S S2 | s
S2 → else S | ε
}
s = S
2. Geben Sie, falls möglich, eine LL(1)-Grammatik für das Dangling-Else-Problem
an. Suchen Sie ggf. im Web nach alternativen Definitionen.
3. Die Sprache PL/0 ist eine vereinfachte Programmiersprache. Prof. Niklaus Wirth
verwendete Sie als Musterbeispiel zur Compilerentwicklung. Die Sprache kann nur
mit Zahlenwerten umgehen und ist nicht dazu gedacht, wirklich eingesetzt zu werden.
Verwenden Sie kfG-Edit um die LL(1)-Forderungen von G zu überprüfen. Verwenden Sie Kopieren & Einfügen“ aus dem PDF-Dokument, um die Produktionsre”
geln der Grammatik zu übertragen. Leiten Sie einige Eingabewörter w ∈ L(G) ab.
Beachten Sie, dass Sie in kfG-Edit bei der Eingabe von w mehrzeichige Terminale
wie begin in Hochkommas einfassen müssen.
program
block
const1
->
->
->
|
const2
->
|
var1
->
var2
->
proc1
->
proc2
->
statement ->
|
|
|
|
|
|
|
statements ->
|
condition ->
|
condition2 ->
|
|
expression ->
|
expblock
->
|
term
->
termblock ->
|
factor
->
ident
->
ident2
->
Char
->
|
|
block .
const1 var1 proc1 statement
const ident = Number const2 ;
EPSILON
, ident = Number const2
EPSILON
var ident var2 ; | EPSILON
, ident var2 | EPSILON
proc2 proc1 | EPSILON
procedure ident ; block ;
begin statement statements end
if condition then statement
while condition do statement
ident := expression
! expression
? ident
call ident
EPSILON
; statement statements
EPSILON
odd expression
expression condition2
# expression | < expression
<= expression | = expression
> expression | >= expression
+ term expblock | - term expblock
term expblock
+ term expblock | - term expblock
EPSILON
factor termblock
* factor termblock | / factor termblock
EPSILON
( expression ) | ident | Number
Char ident2
Char ident2 | EPSILON
_ | a | b | c | d | e | f | g | h | i | j | k | l
m | n | o | p | q | r | s | t | u | v | w | x | y
z
Number
Number2
Digit
-> Digit Number2
-> Digit Number2 | EPSILON
-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Entwickeln Sie mit VCC einen LL(1)-Parser, der nichts ausgibt, wenn der eingelesene Quelltext zur Sprache PL/0 gehört (also syntaktisch korrekt ist). Versuchen
Sie es ggf. mit dem folgenden PL/0-Programm. Es ist syntaktisch korrekt. Wenn
alles geklappt hat, bauen Sie auch mal einen kleinen Syntaxfehler ein. Dann gibt
der Parser syntax error aus.
var x, y, z, q, r, n, f;
procedure multiply;
var a, b;
begin
a := x; b := y; z := 0;
while b > 0 do
begin
if odd z then z := z + a;
a := 2 * a;
b:= b/2
end
end;
procedure divide;
var w;
begin
r := x; q := 0; w := y;
while w <= r do w := 2 * w;
while w > y do
begin
q := 2 * q; w := w / 2;
if w <= r then
begin r := r - w; q := q + 1
end
end
end;
procedure gcd;
var f, g;
begin
f := x; g := y;
while f # g do
begin
if f < g then g := g - f;
if g < f then f := f - g
end;
z := f
end;
procedure fact;
begin
if n > 1 then
begin
f := n * f;
n := n - 1;
call fact
end
end;
begin
?x; ?y; call multiply; !z;
?x; ?y; call divide; !q; !r;
?x; ?y; call gcd; !z;
?n; f := 1; call fact; !f
end.
Lösungen bzw. Lösungshinweise:
1. Aufgabe:
a) Forderung 2 nicht erfüllt, da First- und Followmenge von X nicht disunkt.
FIRST (X) = {d,ε}
FOLLOW (X) = {d}
b) Beide Forderungen werden erfüllt → LL(1)-Grammatik.
c) Forderung 1 nicht erfült, da Firstmengen von S und S else S identisch.
FIRST(S) = { if, s}
FIRST(S else S) = { if, s}
d) Forderung 2 nicht erfüllt, da First- und Followmenge von S2 nicht disunkt.
FIRST (S2) = {else,ε}
FOLLOW (S2) = {$, else}
2. Aufgabe:
Nicht möglich, Alternative in Programmiersprachen durch Klammersetzung oder
Einrückung.
© Copyright 2024 ExpyDoc
