Syntaktická analýza.

Ciele

  1. Precvičiť základné vlastnosti gramatík. krok 1
  2. Precvičiť určovanie množín FIRST a FOLLOW krok 2
  3. Precvičiť typy odvodení a odvodzovacie stromy. krok 3

Úvod

Tematický zámer cvičenia je rozdelený do dvoch logických celkov. V prvej (teoretickej) časti cvičenia sa venuje čas precvičeniu a upevneniu vedomostí nadobudnutých na prednáške: určenie základných vlastností gramatík a vlastností z nej vyplývajúcich, určenie množín FIRST a FOLLOW potrebných vo fáze syntaktickej analýzy.

Postup

Krok 1 cieľ 1

Úloha 1.1

Daná je nasledujúca gramatika:

SABAxB | εByA | zB

Odpovedzde na nasledujúce otázky týkajúce sa uvedenej gramatiky:

  1. Vymenujte terminály a neterminály.
  2. Vymenujte aspoň štyri príklady reťazcov jazyka definovaného danou gramatikou.
  3. Nakreslite odvodzovací strom pre čiastočnú deriváciu SxyyA
  4. Je táto čiastočná derivácia ľavá alebo pravá?
  5. Uveďte príklad čiastočnej derivácie z S v dvoch krokoch pomocou pravej derivácie.

Krok 2 cieľ 2

Úloha 2.1

Daná je nasledujúca gramatika:

ABCBAx | x | εCyC | y | ε

Nájdite množiny FIRST(-) a FOLLOW(-) pre neterminály A, B, C.

Úloha 2.2

Daná je nasledujúca gramatika:

ProgStmtStmtif Expr then BlockStmtwhile Expr do BlockStmtExpr;ExprTermidExprisZero TermExprnot ExprExpr++ idExpr idTermidTermconstBlockStmtBlock{Stmts}StmtsStmt StmtsStmtsε

Nájdite množiny FIRST(-) a FOLLOW(-) pre jednotlivé neterminály.

Krok 3 cieľ 3

V tomto kroku navrhneme gramatiku pre implementáciu vreckovej kalkulačky aritmetických výrazov. Tento typ kalkulačky obvykle nezohľadňuje štandardné matematické priority operátorov, avšak môže obsahovať zátvorky.

Úloha 3.1

Zostrojte gramatiku pre vreckovú kalkulačku, v ktorej operátory sčítania, odčítania, násobenia (príp. celočíselného delenia) majú štandardnú asociatívnosť a rovnakú prioritu. Jazyk nech obsahuje aj zátvorky.

Nájdite dve rôzne najľavejšie odvodenia vety id+idid a zostrojte príslušné odvodzovacie stromy.