Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Kompilatory > Parser > Flashcards

Parser Flashcards

(71 cards)

Start Studying
1
Q

Czy bison może własną wersje yyerror niezależną od skanera?

A

Tak, może. Nawet z taką samą sygnaturą.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Reguły o większym priorytecie powinny znaleść się bliżej symbola startowego, czy dalej?

exp: exp ADD exp
| exp MUL exp

A

Dalej, jak w poniższym listingu

exp : factor
| exp ADD factor

factor : term
| factor MUL term

Wtedy w drzewie wyprowadzeń bliżej liści będą wyrażenia z mnożeniem, a nie dodawaniem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Czy bison w najprostszej formie jest w stanie parsować wieloznaczną gramatykę?

A

Nie jest.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Kiedy bison nie dostanie żadnego tokena ze skanera nastąpi błąd?

A

Tak, błąd składni.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Jak nazywa się najsłabszy język formalny?

A

Język regularny

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Na czym polega słabość języków regularnych?

A

Potrafią rozpoznawać skończoną liczbę stanów.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Czy następujący język jest regularny?

{ (^i )^i | i >= 0}

A

Nie jest regularny, zawiera nieograniczoną liczbę stanów, które nie mogą zostać zbalansowane.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Co na wejście dostaje parser?

A

Ciąg tokenów

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Co wyprowadza na wyjście parser?

A

Drzewo parsowania.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Czy w każdym przypadku parser zwraca drzewo wyprowadzeń?

A

Nie koniecznie, może robić to niejawnie, np. nie powstaje faktyczne drzewo, ale kolejność wykonywania akcji jest zgodna z przechodzeniem po takim drzewie.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Czy aktualnie wykorzystywane parsery są na tyle mocne aby połączyć fazę analizy leksykalnej z parsowaniem?

A

Tak, jest to możliwe.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Jakie elementy definiują gramatykę CFG?

A
  • Nieterminale
  • Terminale
  • Symbol startowy należący do nieterminali
  • Produkcje
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Zapisz definicję produkcji z opisem składników je tworzących.

A

X -> Yi…Yn

X - nieterminal

Y - nieterminal lub terminal lub epsilon (symbol pusty)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Wyjaśnij na przykładzie jednej produkcji rekurencyjność gramatyk CFG.

A

S -> ( S )

Nieterminal S jest jednocześnie lewą i prawą stroną produkcji

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Zapisz formalnie przynależność pewnego ciągu tokenów do języka opisanego przez CFG.

A

{ ai..an | dla kazdego i ai nalezy do zbiory T oraz S -*-> ai..an }

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Terminale w fazie parsowania to które elementy fazy analizy składniowej?

A

tokeny

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Czy mogą istnieć reguły produkujące, które są w stanie zamienić terminale?

A

Nie mogą

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Grupując wiele produkcji dla jednego nieterminala, jakiego skrótu użyć?

A

X -> z

X-> Aa

zamieniamy na

X -> z

   |  Aa
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Czym są prawe strony produkcji?

A

Są to podstawienia, które należy wykonać kiedy na wejściu pojawi się pasujący ciąg tokenów

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Czy lewostronne i prawostronne wyprowadzenia są równoważne?

A

Tak, są równoważne

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Co oprócz przynależności do języka można uzyskać podczas parsowania?

A

Drzewo wyprowadzeń

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Jakiego typu elementy spotykamy w liściach drzew wyprowadzenia?

A

Terminale, inaczej tokeny

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Jakiego typu elementami są węzły drzewa wyprowadzeń?

A

Są to nieterminale.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Wymień dwa sposoby wyprowadzenia (sekwencje produkcji)

A
  • liniowo, S -> aXa -> abCa -> abza
  • drzewo wyprowadzeń
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Co pozwala uzyskać przejście (in-order) po drzewie?
oryginalne wejście
26
Co dodatkowego pokazuje drzewo wyprowadzeń?
Asocjacje pomiędzy operacjami (priorytety)
27
Czy istnieją inne sposoby wyprowadzeń niż lewo i prawostronne?
Tak, istnieją.
28
Kiedy gramatykę nazywamy niejednoznaczną?
Kiedy można skonstruować więcej niż jedno drzewo wyprowadzeń (lewo lub prawostronne) dla pewnego napisu
29
Czy niejednoznaczność stwarza jakieś problemy?
Tak, rozumienie a co za tym idzie rownież wykonanie programu może byc błędne
30
W jaki sposób poradzić sobie z niejednoznacznościami?
* przepisać gramatykę * wykorzystać skojarzenia (**%left** ) oraz priorytet (**%prec**) w bison'ie
31
Który operator posiada pierwszeństwo? %left + %left \*
ostatni na ilście posiada pierwszeństwo, czyli operator **\*** (mnozenia)
32
Jakie znasz mechanizmy reakcji na błędy w kompilatorach?
* tryb paniki * dodawanie produkcji * próba naprawy
33
Jaki jest cel kompilatora oprócz translacji poprawnego kodu?
Wykrycie nie prawidłoych programów
34
Jakie akcje wykonuje kompilator w trybie paniki?
* Próbuje usunąć wejście do pewnego określonego symbolu * Kontrynuuje od tego miejsca (następuje restart)
35
Jaka będzie akcja ratownicza dla następującego, błędnego wejścia? (1 +**+ **2) + 3
Skok do liczby całkowitej po zauważeniu drugiego znaku + i kontynuacja wykonania.
36
Jak nazywa się specjalny token w bison'ie służacy do określenia ile z wejściowego ciągu tokenów będzie pomijanych?
**error**
37
Podaj przykład na pominięcie całego bloku w nawiasach okrągłych.
E -\> E + E | ( E ) | **( error )** Gdy nie będzie w stanie dla reguły E zredukować wyrażenia w nawiasie, pominie całe to wyrażenie
38
Podaj przykład na wprowadzenie dodatkowych produkcji podczas wykrycia błędu.
Np. dla wyrażeń 5 \* x , jeżeli użytkownicy używają notacji 5 x, można dodać nową produkcję do zestawu używanych E -\> E \* E | **E E**
39
Jakie są wady wprowadzania nowych produkcji dla błędnych wyrażeń?
* dodane produkcje komplikują gramatykę * promuje się błędne użycie kompilatora
40
Jaka idea kryje się za korektą błędnych programów?
Znalezienie "bliskiej" wersji programu, która jest wolna od błędów
41
Jakich mechanizmów używa się do korekty błędów?
* dodawanie/usuwanie tokenów * wyczerpujące przeszukiwanie
42
Wymień najbardziej znany kompilator korygujący błędy.
PL/C dla PL/I
43
Od czego pochodzi skrót PL/C?
PL Correction vs. Cornell
44
W jakim celu stworzono w przeszłości bardzo rozbudowane kompilatory korygujące?
* powolny cykl rekompilacji (dochodził do jednego dnia) * wystarczył jeden błąd aby stracić ten dzień
45
W jakiej kolejności konstruowane jest drzewo parsowania dla parsera rekursywnie schodzącego?
Od wierzchołka drzewa parsowania, od lewej do prawej, tj. produkcje będą wybierane od pierwszej z listy a nieterminale będą podmieniane w kolejności od lewej do prawej.
46
W jakiej kolejności w drzewie wyprowadzeń pojawiają się nieterminale?
W takiej kolejności jak były zapisane w strumieniu tokenów
47
Jakie podejście zmiany gramatyki stosuje się do rekursywnego parsera zstępującego, jeżeli dla danego nieterminala można wymienić co najmniej dwie produkcje, które zwrócą logiczną prawdę
Należy zastosować lewostronne faktorowanie
48
Dlaczego lewostronna rekurencja jest fatalna dla parsera rekursywnie zstępującego?
Ponieważ w tym przypadku symbole są podstawiane od lewej do prawej, jeżeli wystąpi rekurencja z lewego końca produkcji, parser nigdy nie przerwie pracy.
49
W jaki sposób leczy się lewostronną rekurencję? S -\> S a | b
Zamienia się ją w prawostronną rekurencję jak poniżej S-\> b S' S' -\> a S' | epsilon
50
Czy parser przewidujący jest typu z góry na dół?
Tak, jest typu top down
51
Czy parser przewidujący używa mechanizmu back-tracking?
Nie używa
52
Co pozwala parserowi przewidującemu wybrać dobrą produkcję?
Patrzenie w przód o pewną liczbę tokenów.
53
Co oznaczają poszczególne znaki w definicji gramatyki typu LL(k)?
L - czytanie od lewej do prawej L - lewostronne wyprowadzenie k - patrzenie w przód o tyle tokenów
54
Podaj definicję zbioru First(X)
First(X) = { t | X -\>\* tA } v { epsilon | X -\>\* epsilon }
55
Kiedy gramatyka nie jest LL(1)?
Kiedy w tablicy parsowania **T** jest więcej niż jedna pozycja dla danego wiersza i kolumny.
56
Najprostszy lub najkorzystniejszy pod jakimś wzlędem (SJP)?
Kanoniczny.
57
Które gramatyki gwarantują brak parsera LL(1)?
* nie poddana lewostronnej faktoryzacji * lewostronnie rekurencyjna * wieloznaczna
58
Czy istnieją ogólne wydajne algorytmy rozpoznawania uchwytów?
Nie istnieją dla ogólnych gramatyk CFG
59
Czy istnieją heurystyki zgadujące uchwyty?
Tak, istnieją
60
Jaki nadrzędny zbiór gramatyk CFG zawiera gramatyki typu SLR(k)?
LALR(k)
61
Jaki nadrzędny zbiór gramatyk CFG zawiera gramatyki typu LALR(k)?
LR(k)
62
Jaki nadrzędny zbiór gramatyk CFG zawiera gramatyki typu LR(k)?
Gramatyki jendoznaczne.
63
Jaki nadrzędny zbiór gramatyk CFG zawiera gramatyki jednoznaczne?
Wszystkie gramatyki CFG.
64
Kiedy alfa jest możliwym prefiksem?
Kiedy istnieje omega, taka że stan alfa | omega jest dopuszczalnym stanem w parserze typu przesunięcie-redukcja
65
Co widzi parser na każdym etapie parsowania?
Widzi stos, nie widzi natomiast reszty wejścia (poza mały lookahead)
66
Jakim jezykiem jest zbiór możliwych prefiksów dla każdej gramatyki?
Językiem regularnym.
67
Czym jest pozycja?
Jest to produkcja ze znakiem kropki (.) po prawej stronie produkcji.
68
Wypisz wszystkie składniki dla poniższej produkcji ## Footnote **E -\> ( T )**
* E -\> . ( T ) * E -\> ( . T ) * E -\> ( T . ) * E -\> ( T ) .
69
Wymień składniki dla produkcji jak niżej ## Footnote **X -\> *epsilon***
Dla epsilona istnieje jedna kropka * X -\> .
70
Jak inaczej nazywa się składniki (items)?
Składniki **LR(0)**
71
Jaki związek zachodzi pomiędzy znakami przed . (kropką) prawidłowego składnika a stosem?
Wszystko po lewej stronie przed kropką ma znajdować się na szczycie stosu.

Kompilatory (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions