Cvičenia
Cvičenie 2
Slajdy z prednášky
1. Eliminácia ľavej rekurzie a Left factoring, množiny first a follow
Majme nasledovné gramatiky:
- S → 0S1 | 01
- S → +SS | *SS
- S → S(S)S | epsilon
- S → S+S | SS | (S) | S* | a
- S → (L) | a
L → L,S | S
Eliminujte ľavú rekurziu, faktorizujte ich podľa ľavej strany a vytvorte množiny first a follow. Zostrojte Predictive Parsing Table.
2. Napíšte triedu Parser, ktorá dostane vo vstupnom súbore (zrejme v konštruktore) popis LL(1) gramatiky a zostrojí množiny
FIRST(A) pre každý znak abecedy gramatiky a
FOLLOW(A) pre každý neterminál gramatiky (teda zrejme si tieto množiny uchová v nejakej tabuľke).
- Pridajte metódu constructTable(), ktorá na základe množín FIRST a FOLLOW potom skonštruuje Predictive Parsing Table.
- Do triedy pridajte metódu parse(String fileName), ktorá dostane na vstup súbor a bude postupne zostrojovať odvodenie textu v súbore podľa danej gramatiky.
Cvičenie 1
1. Vytvorte triedu
FASimulator, ktorá bude implementovať konečný automat, t.j. zo súboru načíta popis automatu a simuluje ho na vstupe z druhého súboru.
2*. Uvažujme nasledujúcu "bezkontextovú" gramatiku jednoduchého programovacieho jazyka
(IDENTIFIER reprezentuje identifikator t.j. reťazec z písmen a čísel, prvý znak musí byť písmeno,
NUMBER reprezentuje nejaké číslo), kde slová veľkými písmenami reprezentujú terminály a malými neterminály:
program → PROGRAM [declarations] BEGIN command_sequence END
declarations → INTEGER id_seq.
id_seq → IDENTIFIER | id_seq, id_seq
command_sequence → command | command command
command → - NIC; /*prazdny prikaz - nevykona nic*/
-
- | IDENTIFIER := expression;
- | IF expression THEN command_sequence ELSE command_sequence FI;
- | WHILE expression DO command_sequence END;
- | READ IDENTIFIER;
- | WRITE expression;
expression →
- NUMBER | IDENTIFIER | (expression)
- | expression + expression | expression - expression
- | expression*expression | expression/expression
- | expression^expression
- | expression = expression | expression < expression
- | expression > expression
a). Napíšte regulárny výraz, ktorý bude reprezentovať tokeny pre programy napísané podľa uvedenej gramatiky
b). Vytvorte triedu
Scanner, ktorá bude obsahovať metódu:
- dalsiToken() - ktorá bude postupne vracať rozpoznané tokeny.
Nezabudnite ošetriť chybne zapísané programy a vypísať chybové hlásenia.