Celočíselná kalkulačka pomocou Lex a Yacc

Ciele
  1. Oboznámiť sa s princípom fungovania generátorov Lex a Yacc.
  2. Oboznámiť sa s integrovaným Prostredím pre vývoj prekladačov (PPVP).
  3. Oboznámiť sa so štruktúrou vstupných súborov Lex a Yacc a spôsobom špecifikácie gramatiky.
  4. Naučiť sa pridávať pravidlá pre lexikálny analyzátor, syntaktický analyzátor a špecifikovať sémantické akcie.
Úvod
    Téma vývoja prekladačov programovacích jazykov sa veľmi často opakuje vo výučbe informatiky. Je na to niekoľko dôvodov.
    • Prekladač programovacieho jazyka je základným nástrojom programátora, a preto je užitočné poznať princíp jeho fungovania.
    • Princípy syntaktickej analýzy neplatia len pre programovacie jazyky, ale môžu byť použité pre analýzu ľubovoľného vstupu, ktorý sa dá opísať pomocou vhodnej gramatiky (regulárnej, bezkontextovej). Analýza sa môže týkať špecializovaných jazykov (robotické jazyky, komunikačne jazyky, jazyky pre popis scén, štruktúr,...), údajové vstupy s presne definovaným formátom a syntaxou a pod.
    • Technológie vývoja syntaktických analyzátorov pomocou generátorov sú vynikajúcim príkladom použitia generatívneho prístupu k vývoju softvéru. Umožňujú automaticky generovať časť implementácie programu z deklaratívnej špecifikácie.
Postup
  1. Nástroje Lex a Yacc umožňujú automaticky generovať lexikálny a syntaktický analyzátor z popisu gramatiky jazyka. Po rozšírení gramatických pravidiel o atribúty symbolov (pomocou tzv. pozičných premenných $1,$2,..$$...budú vysvetlené ďalej), o sémantické funkcie na spracovanie atribútov (definujú sa v jazyku C) a o funkcie zabezpečujúce interpretáciu alebo preklad rozpoznanej jazykovej konštrukcie, je možné pomocou generátorov Lex a Yacc vygenerovať kompletný kód syntaxou riadeného editora, syntaxou riadeného interpretačného alebo kompilačného prekladača.Vstupom pre Lex a Yacc sú súbory obsahujúce špecifikáciu lexikálnej a syntaktickej analýzy (po doplnení atribútov a sémantických pravidiel obsahujú aj špecifikáciu sémantického spracovania, interpretácie resp. generovania kódu) a výstupom sú zdrojové kódy vygenerovaných častí prekladača v implementačnom jazyku C. Po ich preložení prekladačom jazyka C (na obrázku označený ako CC -- C compiler) vznikne prekladač vyvíjaného jazyka schopný analyzovať vstupný súbor, generovať príslušný preložený výstup alebo ho priamo interpretovať (vykonávať).
  2. Plugin PPVP (Prostredie pre vývoj prekladačov) pre NetBeans poskytuje integrované prostredie umožňujúce používať nástroje Lex a Yacc, presnejšie ich novšie alternatívy -- Flex a Bison.
    Úloha: Stiahnite si zdrojové texty projektu jednoduchého celočíselného kalkulátora a rozbaľte ho. Spustite NetBeans a otvorte projekt.
    Úloha: Skomilujte projekt pomocou tlačidla kladivo a následne spustite kalkulátor stlačením tlačidla trojuholník v paneli nástrojov. Vyskúšajte zadať jednoduché aritmetické výrazy. Aké výrazy dokáže kalkulačka spracovať a aké nie?
  3. Vstupom nástroja Lex je špecifikačný súbor (prípona .l), jeho výstupom je zdrojový súbor analyzátora v jazyku C (lex.yy.c). Ten obsahuje definíciu funkcie int yylex() reprezentujúcej lexikálny analyzátor. Všeobecná štruktúra vstupného súboru pre Lex je nasledovná:

    %{
        C-deklarácie
    %}
    LEX-deklarácie
    %%
    pravidlá
    %%
    funkcie

    Súbor sa skladá z troch sekcií. V prvej sú deklarácie. Môžu sa tu nachádzať príkazy v jazyku C (uvedené medzi {% a %}), ktoré sa bez zmeny skopírujú do úvodnej časti vygenerovaného súboru. Okrem toho tu môžete uviesť deklarácie substitučných reťazcov v tvare:

    meno substitučný-reťazec

    V ďalšej časti sú samotné pravidlá opisujúce lexikálny analyzátor. Pravidlá sa zapisujú každé na samostatný riadok ako regulárny výraz nasledovaný blokom príkazov v jazyku C, ktorý sa má vykonať v prípade, že vstupný text vyhovuje regulárnemu výrazu. Teda:

    regulárny-výraz { C-príkazy }

    Regulárny výraz je postupnosťou symbolov a operátorov s nasledovným významom:

    X znak X (nie operátor)
    "X" znak X
    \X esc-znak \X (\n,\t,...)
    "XYZ" reťazec XYZ
    [XYZ] znak X alebo Y alebo Z
    [X-Z] znak X alebo Y alebo Z
    [^XYZ] ľubovoľný znak okrem X,Y,Z
    . ľubovolný znak okrem \n
    (R) R
    R? nepovinné R
    R* 0,1,2,... opakovaní R
    R+ 1,2,3,... opakovaní R
    R|S R alebo S
    {M} substitúcia za M

    Príkazy vykonávané pri nájdení textu vyhovujúcemu regulárnemu výrazu môžu používať špeciálne premenné: int yyleng - dĺžka rozpoznaného reťazca, char yytext[] - rozpoznaný reťazec FILE *yyin - súbor, z ktorého sa číta (implicitne "stdin")

    Tretia časť súboru je určená pre definície funkcií v jazyku C. Väčšinou tu stačí definovať funkciu int yywrap(), ktorá je vyvolaná v prípade, že sa dosiahne koniec súboru. Táto funkcia môže v prípade potreby otvoriť iný súbor alebo jednoducho vrátiť hodnotu 1, ktorá označuje koniec čítania vstupu.

  4. Vstupom nástroja Yacc je špecifikačný súbor s príponou .y a s podobnou štruktúrou ako pri nástroji Lex. Výstupom je zdrojový súbor analyzátora v jazyku C. V tomto súbore je definovaná funkcia int yyparse(), ktorá reprezentuje syntaktický analyzátor. Všeobecná štruktúra vstupného súboru je takáto:

    %{
        C-deklarácie
    %}
    YACC-deklarácie
    %%
    pravidlá
    %%
    funkcie

    Yacc deklarácie môžu byť napríklad:

    • Určenie začiatočného symbolu: %start meno
    • Definície terminálnych symbolov: %token meno1 meno2
    • Určenie priority a asociatívnosti operatorov (v jednom riadku majú rovnakú prioritu, smerom dole priorita vzrastá):
      %left op1 op2 ... ľavoasociatívne
      %right op3 op4 ... pravoasociatívne
      %nonassoc op5 op6 ... neasociatívne

    V druhej časti špecifikačného súboru sa definujú pravidlá gramatiky jazyka. Pravidlo má tvar: neterminál: symbol1 symbol2 ... ; Pri pravidle tiež môže byť uvedená činnosť, ktorá sa má vykonať v prípade rozpoznania daného pravidla v analyzovanom texte: neterminál: symbol1 symbol2 ... { C-príkazy }; V prípade, že je neterminál definovaný niekoľkými pravidlamí, tie sú združené takto:

    neterminál: pravá_strana_1
              | pravá_strana_2
              ...
              ;

    Činnosť pri pravidlách je špecifikovaná pomocou bloku príkazov jazyka C (tzv. sémantické funkcie). V týchto príkazoch je možné používať aj špeciálne premenné - tzv. pozičné premenné v tvare $$ a $i. Tieto premenné umožňujú odpamätavať vlastnosti (atribúty) symbolov gramatiky (terminálov a neterminálov). Umožňujú aj prenos hodnôt medzi symbolmi a vypočítavanie nových hodnút atribútov podľa potreby sémantického spracovania. Premenná $$ reprezentuje hodnotu atribútu neterminála na ľavej strane pravidla a úlohou sémantických funkcií pripojených k pravidlu je zvyčajne výpočet tejto hodnoty. Premenné $i, kde i je celé číslo, reprezentujú hodnoty atribútov jednotlivých symbolov na pravej strane pravidla (číslované sú od 1).

  5. Pre spoločné použitie Lex a Yacc je potrebné v špecifikačnom súbore pre Lex v akciách pri nájdení lexikálnych symbolov jazyka:

    1. vrátiť kód lexikálneho symbolu: return(SYMBOL);
    2. nastaviť hodnotu atribútu lexikálneho symbolu: yylval= hodnota;

    V špecifikačnom súbore nástroja Yacc je zase potrebné pripojiť kód vygenerovaného lexikálneho analyzátora: #include "lex.yy.c"

    Potom je možné vytvoriť zdrojové súbory analyzátorov pomocou príkazov:

    lex priklad.l
    yacc priklad.y

    a vytvoriť spustiteľný súbor:

    gcc priklad.tab.c

    alebo použiť PPVP plugin pre NetBeans.

  6. Prezrite si pravidlá lexikálnej a syntaktickej analýzy uvedené v špecifikačných súboroch kalkulačky.
    Úloha: Upravte calc1.l a calc1.y tak, aby kalkulačka umožňovala:
    1. umocňovanie: x^ má význam x*x
    2. faktoriál: x! má význam 1*2* ... * x (x>0)
    3. posun doľava: x<<y má význam posunu x o y-bitov doľava
    4. posun doprava: x>>y má význam posunu x o y-bitov doprava
Zdroje
  1. PPVP - NetBeans plugin pre vývoj prekladačov
  2. Nástroje Flex (lex), Bison (yacc) a GCC využívané pluginom.
  3. Zdrojové kódy pre cvičenie 1
  4. Makefile pre zostavenie prekladača bez NetBeans pluginu
  5. Prednáška 01 - Jazykové systémy a jazykové procesory - Prostriedky pre analýzu a návrh jazykových procesorov
Doplňujúce zdroje
  1. Úvod do nástrojov Lex a Yacc
  2. Manuál nástroja Flex
  3. Manuál nástroja Bison
  4. Lesk, Schmidt: Lex − A Lexical Analyzer Generator
  5. Johnson: Yacc: Yet Another Compiler-Compiler
  6. Stručne poznámky k nástroju Lex
comments powered by Disqus