Hľadaj Zobraz: Univerzity Kategórie Rozšírené vyhľadávanie

44 761   projektov
0 nových

Konštrukcia prekladačov (prednáška 3) - Syntaktická analýza zdola - nahor SA↑

«»
Prípona
.ppt
Typ
prezentácia
Stiahnuté
0 x
Veľkosť
0,3 MB
Jazyk
slovenský
ID projektu
13860
Posledná úprava
09.09.2021
Zobrazené
625 x
Autor:
-
Facebook icon
Detaily projektu
Popis:
Konštruuje sa derivačný strom od listov ku koreňu
Vytvára sa pravý rozklad analyzovanej vety - postupnosť pravých vetných foriem v opačnom poradí
Modelom SA↑ je RZA
...
SA↑ rieši nasledujúce úlohy:
1. nájdenie jadra vetného tvaru 
(redukčná časť vetného tvaru, l-fráza -najľavejšia jednoduchá fráza vetnej formy)
2. redukcia jadra vetného tvaru (l-frázy a) na príslušný neterminál A (podľa odpovedajúceho gramatického pravidla A → a).
...
Princíp SA↑ s návratmi:
1. Presúvaj symboly zo vstupu do zásobníka, kým nie je na vrchole a (A  a  P)
2. Redukcia jadra a na vrchole zásobníka na neterminál A
Ak existuje viac pravidiel s rovnakou pravou stranou, systematicky ich skúšame použiť na redukciu.
3. Pokračuj na 1.
4. Ak je celý vstup prečítaný a žiadnu redukciu nie je možné uskutočniť, návrat na 2.
Návrat k miestu poslednej redukcie a použije sa iné pravidlo s pravou stranou rovnou jadru.
Ak to nepomôže, po návrate do stavu poslednej redukcie sa hľadá iné jadro.
5. Ak je v zásobníku len štartovací symbol a celý vstup je prečítaný, veta je prijatá.
...

Kľúčové slová:

syntaktická analýza

derivačný strom

nedeterminizmus

gramatika

jazyk

perspektívna predpona

derivácia

rozšírená gramatika

GOTO

funkcia GOTO

rozkladová tabuľka



Obsah:
  • Syntaktická analýza zdola - nahor SA↑ - bootom up parsing
    Syntaktická analýza zdola - nahor SA↑ - princípy
    Princíp SA↑ s návratmi
    Nedeterminizmus pri syntaktickej analýza zdola - nahor
    Deterministická SA zdola - nahor - LR(k) jazyky
    LR(k) gramatiky - základné pojmy a definície
    Príklad gramatiky, ktorá nie LR(k) pre žiadne k
    SYNTAKTICKÁ ANALÝZA PRE LR(k) JAZYKY
    PRÍKLAD
    Algoritmus konštrukcie LR(k) správnych položiek pre perspektívnu predponu t
    PRÍKLAD
    Algoritmus konštrukcie systému LR(k) správnych položiek pre gramatiku G.
    PRÍKLAD
    Reprezentácia GOTO funkcie pomocou LR automatu
    Rozkladová tabuľka pre LR(k) SA
    PRÍKLAD
    KOLÍZIE PRI ANALÝZE ZDOLA - NAHOR
    Algoritmus pre test LR(k) podmienky
    Algoritmus syntaktickej analýzy pre LR(k) jazyky
    Príklad

Zdroje:
  • poznámky
  • prednášky
  • skriptá