Formálne jazyky

Úvod do syntaktickej analýzy.

Ciele

  1. Zápočtový test č. 1.
  2. Opakovanie a prehĺbenie učiva. Riešenie úlohy so zameraním na konštrukciu gramatiky podľa danej špecifikácie.
  3. Pochopenie konštrukcie syntaktického analyzátora.
  4. Prvé zadanie.

Úvod

Cieľom cvičenia je pochopenie a následná implementácia gramatiky pre projekt kalkulačky. Prvým krokom je vytvorenie gramatiky podľa obvyklých matematických pravidiel pre operátory. V ďalšom kroku je potrebné uskutočniť dekompozíciu a určiť, z akých tried bude riešenie pozostávať. Následne je možné pristúpiť k samotnej implementácii.

Postup

Krok 1

Prvá časť cvičenia je venovaná absolvovaniu zápočtového testu č. 1. Je potrebné postupovať podľa pokynov vyučujúceho.

Krok 2

V tomto kroku si zopakujeme základné vlastnosti gramatík.

Úloha 2.1

Daná je nasledujúca gramatika:

S → SS+ | SS* | a.

Vyriešte nasledujúce úlohy:

  1. Uveďte, akého typu je daná gramatika.
  2. Nájdite odvodenie reťazca aa+a* v danej gramatike.
  3. Skonštruujte strom odvodenia pre daný reťazec.
  4. Aký jazyk generuje táto gramatika? Svoju odpoveď zdôvodnite.

Krok 3

Na základe gramatiky jazyka je možné implementovať jeho syntaktický analyzátor. Jedným zo spôsobov, ako to realizovať, je vytvorenie rekurzívneho analyzátora pracujúceho metódou zhora-nadol. Hlavným princípom jeho implementácie je vytvorenie funkcie pre každé pravidlo gramatiky, kde postupnosť krokov v tele funkcie zodpovedá postupnosti symbolov na pravej strane pravidla. Preštudujte si schému implementácie takéhoto syntaktického analyzátora v tabuľke dole.

EBNF Implementácia
A → ... Definícia A() { ... }
Neterminal A Volanie A()
Terminal a if (symbol == a) next_symbol(); else error();
{ X } while (symbol == first(X) ) { ... }
[ X ] if (symbol == first(X) ) { ... }
X | Y | Z switch (symbol) { case first(X) : ... }

Následne sa proces analýzy spustí prečítaním prvého lexikálneho symbolu a zavolaním funkcie štartovacieho symbolu gramatiky.

Častým problémom pri preklade výrazov je však

  • (1) určenie poradia, v akom sa operácie majú vykonávať, a tiež
  • (2) ukladanie medzivýsledkov výpočtu.

Riešením prvého problému je prevod výrazu do postfixnej formy, kde sa operácie vykonávajú v tom poradí v akom sa vyskytujú. Riešením druhého problému je použitie zásobníka. Princíp výpočtu výrazu 1 * 2 + 3 * 4 v postfixnom tváre s použitím zásobníka je znázornený na obrázku.

Výpočet výrazu s využitím zásobníka
Obr. 2: Výpočet výrazu s využitím zásobníka

Pri preklade výrazu je teda dostatočné vygenerovať postupnosť operácií vloženia hodnoty do zásobníka a výpočtu s hodnotami na vrchole zásobníka.

Úloha 3.1

Prepíšte do postfixného tvaru výraz "(x+y)*(x-y)".

Úloha 3.2

  • Akým spôsobom získame postfixný tvar výrazu? Aké údajové štruktúry a aké metódy vieme použiť?
  • Ako by ste definovali prefixný tvar výrazu?

Krok 4

V tomto kroku sa oboznámime s prvým zadaním. Zadanie je potrebné vypracovať a odovzdať podľa pokynov vyučujúceho.

Úlohou je vytvoriť kalkulačku, ktorá prijíma na vstupe výrazy v tvare reťazca (napr. (1+2)*3-1). Asociativita a priorita jednotlivých operátorov je daná v konkrétnej špecifikácii. Program na vstupe prečíta reťazec a vyhodnotí ho. Výsledkom je teda numerická hodnota (pre daný výraz pri zachovaní štandadrnej priority a asociativity operátorov je to 8).

Je vhodné, aby samotná aplikácia kalkulačky pozostávala z viacerých tried. Možný návrh je na nasledujúcom obrázku.

Diagram tried pre aplikáciu Kalkulačka
Obr. 3: Diagram tried pre aplikáciu Kalkulačka

Úloha 4.1

Oboznámte sa s návrhom tried podľa pokynov vyučujúceho.

V nasledujúcich ukážkach doplňte postupne funkčný kód. Ako základ použite nasledujúcu šablónu.

Úloha 4.2

V triede Main vytvorte inštancie tried Lexer a Parser a odovzdajte triede Lexer prečítaný vstupný reťazec:

try {
   ...
   Lexer lexer = new Lexer(...);
   int result = new Parser(...).statement();

   System.out.printf("\nResult %d\n", result);
} catch (Exception e) {
   ...
}
...

Úloha 4.3

V triede Lexer prečítajte používateľský vstup po znakoch a vyhodnoťte ho: ak sa v reťazci objaví operátor alebo zátvorka, vráťte príslušný token. Ak sa nájde postupnosť číslic (numerál), vypočíta sa hodnota nájdeného numerálu. Ak žiadna podmienka nie je splnená, ohlási sa chyba Neplatný znak.

private void consume() {
   try {
       current = ...    
...

public Token nextToken() {
   ...
   switch (current) {
       case '+':
           consume();
           return Token.PLUS;
       ...
   }

Úloha 4.4

V triede Parser implementuje parsovanie podľa gramatiky - koľko metód pre ktoré neterminály musíte implementovať? Nezabudnite na overenie, či bol prečítaný očakávaný symbol (terminál).

// Expr -> ...
private int expr() {
   int value = mul();
   
   while (symbol == Token.PLUS) {
           ...
   }
   
   return value;
}
...

Poznámka

Vytvorený návrh a kód si odložte pre ďalšie použitie.

© Copyright 2024 KPI FEI TUKE