Analiza składniowa cz. 3

Obsługa błędów

Obsługa błędów składniowych to ważny obszar związany z konstrukcją parserów. Zwykle nie chcemy, aby parser kończył pracę po napotkaniu pierwszego błędu. Zamiast tego parser po pojawieniu się błędu powinien próbować odzyskać kontrolę i znaleźć miejsce, od którego mógłby kontynuować pracę. Bison dostarcza pewnych mechanizmów do tzw. error recovery.

Często w tym procesie wykorzystuje się specjalny predefiniowany token error do wskazania miejsca, gdzie mogą pojawić się błędy składniowe.

Dla przykładu rozważmy regułę:

	instr :  error ';'   { yyerrok; }

Załóżmy, że pojawia się błąd składniowy podczas, gdy parsowany jest nieterminal instr. Co dzieje dalej? W pewnym uproszczeniu można powiedzieć, że parser wypisuje komunikat o błędzie i zdejmuje symbole ze stosu dopóki nie natrafi na token error. Wtedy woła procedurę yyerrok powodującą kontynuację parsingu w normalnym trybie. Opisane wyżej podejście do odzyskiwania kontroli po napotkaniu błedu, tzw. tryb paniki, sprawdza się dobrze w schemacie, gdzie wszystkie instrukcje są zakończone średnikami.

Zazwyczaj, gdy parser znajduje na wejściu błędny symbol wypisuje komunikat o błędzie i rozpoczyna procedurę wychodzenia z błędu poprzez zdejmowanie ze stosu symboli dopóki nie natrafi na stan, który odpowiada akcji shift dla tokenu error. Jeżeli nie ma takiego stanu parser kończy pracę i zwraca wartość 1. Jeżeli znajdzie się taki stan, to wykonuje akcję shift na tokenie error i podejmuje na nowo parsing w specjalnym trybie obsługi błędu (error mode). W tym trybie pomija symbole, aż do momentu, gdy może wykonać legalną akcję shift. Aby pominąć lawinę komunikatów o błędach parser wraca do normalnego trybu po wykonaniu trzech legalnych operacji shift.

Można poczytać trochę na temat strategii error recovery na http://home.agh.edu.pl/~tekomp/ w sekcji "Referaty" i dalej "Przegląd metod error recovery dla parsingu bottom-up". Sporo informacji znajduje się w dokumentacji bisona dostepnej np. na http://dinosaur.compilertools.net/bison/bison_9.html#SEC81. Kilka ciekawych przykładów można znaleźć na http://marvin.ibest.uidaho.edu/~heckendo/CS445/bisonErrorToken.html.

Ćwiczenia

Ćwiczenie 1

Zadanie polega na stworzeniu pseudo-walidatora dla XHTML-a (XHTML 1.0 Specification). Proszę wziąć pod uwagę np. następujące znaczniki:

nagłówki <h1></h1>,<h2></h2>
link <a href=...></a>
paragraf, bold, break <p></p>,<b></b>,<br/>

Dla przykładowego poprawnego pliku:

<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
  <head>
    <title>Test</title>
  </head>
  <body>
    <h1>Opis cwiczenia</h1>
      <p>Zadanie polega na stworzeniu <b>pseudo-walidatora XHTML-a</b>.</p> 
	    
      <h2>W3C Markup Validation Service</h2>       
        <p><a href="http://validator.w3.org/">W3C Markup Validation Service</a><br/>  
        sprawdza zgodnosc dokumentow HTML-owych i XHTML-owych ze specyfikacjami<br/>  
        rekomendowanymi przez <a href="http://www.w3.org">W3C</a></p> 
  </body>
</html>

na wyjściu powinien pojawić się komunikat, że plik jest poprawny:

Natomiast dla niepoprawnego wejścia:

<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
  <head>
    <title>Test</title>
  </head>
  <body>
    Inny opis cwiczenia</h1>
      <p>Zadanie polega na stworzeniu <b>pseudo-walidatora XHTML-a</b>. 
	    
      <h2>W3C Markup Validation Service</h2>       
        <p><a href="http://validator.w3.org/">W3C Markup Validation Service</a><br/>  
        sprawdza zgodnosc dokumentow <i>HTML-owych</i> i XHTML-owych ze specyfikacjami<br/> 
        rekomendowanymi przez <a href="htt://www.w3.org">W3C</a></p> 
  </body>
</html>

na wyjściu powinny pojawić się komunikaty o błędach np. w następującej formie:

Blad w linii  9: niesparowany znacznik </h1>
Blad w linii 11: niesparowany znacznik <p> 
Blad w linii 14: nieznany znacznik <i></i>
Blad w linii 15: nieprawidłowy format znacznika <a href="htt://www.w3.org">W3C</a>

Ćwiczenie 2

Proszę napisać parser, który będzie wykonywał przekształcenie typu:

wejscie	wyjscie
`int licz, tmp, i;`	`int licz; int tmp; int i;`
`real f1, f2;`	`real f1; real f2;`

Ćwiczenie 3

Proszę napisać parser pseudo-Pascala z wykorzystaniem mechanizów error recovery. Parser po pojawieniu się błędu wypisuje odpowiedni komunikat i kontynuuje przetwarzanie.

Materiały pomocnicze: pascal.y, pascal.l, pseudopascal-grammar-bnf.