[ Pobierz całość w formacie PDF ]
.Innym operatorem ułatwiającym konstrukcję wzorców jest operator opcjonalności - znak `?'.Ciąg w? oznacza ciąg w lub ciąg pusty.Możemy również używać symbolu `+', różniącego się od `*' tym, że nie zawiera ciągu pustego.Wzorzec m+ możemy więc zapisać jako m*m.Możemy również określić wprost krotność konkatenacji danego wyrażenia.Krotność tę zapisuje się po danym wyrażeniu, ujętą w nawiasy klamrowe.Specyfikacja generatora Lex zawiera jeszcze operator kropki (`.'), który odpowiada dowolnemu, widzialnemu znakowi.Generator Lex ma wbudowany mechanizm retrakcji, dzięki czemu unika dopasowywania ciągu do wzorcu w sytuacji, w której dłuższy ciąg (rozpoczynający się od dotychczas przeczytanego) mógłby zostać dopasowany.W chwili, gdy ciąg na wejściu został kompletnie dopasowany do jakiegoś wzorca, a zasada najdłuższego dopasowania sugeruje kontynuację dopasowania do innego wzorca, Lex zapamiętuje pozycję w tekście wejściowym i wzorzec, do którego udało mu się już dopasować ciąg wejściowy, a następnie kontynuuje dopasowanie do dłuższego „wzorca” (wzorca, do którego dopasowane tekst będzie dłuższy).W przypadku, gdyby dopasowanie nie powiodło się, Lex wraca do ostatniego dopasowanego wzorca, wykonuję związaną z nim akcję i rozpoczyna analizę od miejsca, w którym zakończył się dopasowany ciąg.Z zaawansowanych technik, które Lex udostępnia użytkownikowi, należy jeszcze wymienić możliwość uwzględniania kontekstu - zarówno prawego, jak i lewego.Pozwala to rozstrzygać sytuacje, w których ten sam ciąg znaków może być różnie potraktowany, w zależności od kontekstu, w którym występuje.Uwzględnianie lewego kontekstu zrealizowano w Lexie za pomocą możliwości korzystania ze stanów początkowych, natomiast uwzględnianie prawego kontekstu za pomocą możliwości konstruowania reguł typu w/p - reguła taka oznacza, że ciąg wejściowy można dopasować do wzorca w tylko wtedy, gdy po tym ciągu występuje ciąg pasujący do p.lAnaliza składniowa - YacclJak wspomniano wcześniej, z analizatora składniowego wyodrębnia się osobny moduł, analizator leksykalny, do zbudowania którego może nam posłużyć Lex.Analizator składniowy jest wtedy modułem nadrzędnym dla analizatora leksykalnego - wykorzystuje wyniki jego pracy.Dobrym narzędziem pomocniczym, służącym do tworzenia analizatorów składniowych, jest YACC - podobnie jak Lex opracowany w amerykańskiej firmie AT&T.YACC może współpracować z Lexem w systemie pionowym (patrz p. IV.4.1).Połączone siły obu narzędzi mogą posłużyć do tworzenia różnorakich translatorów i interpreterów - począwszy od prostego kalkulatora, zakończywszy na kompilatorach skomplikowanych języków programowania.Język i gramatyka bezkontekstowaPierwszym warunkiem, jaki musi spełniać język, aby można było przetwarzać go za pomocą YACCa jest bezkontekstowość jego gramatyki.Oznacza to, że opisując gramatykę języka, specyfikujemy jedną, lub więcej grup syntaktycznych i tworzymy (opisujemy) reguły konstruowania ich z części.Dla przykładu - w języku C taką grupą jest wyrażenie.Jedną z reguł tworzących wyrażenie może być zdanie: „wyrażenie składa się ze znaku minus i innego wyrażenia”.Inną może być zdanie: „wyrażenie może być liczbą całkowitą”.Jak widać, w opisie reguł często stosuje się rekursję, jednak musi istnieć przynajmniej jedna reguła, który rekursję kończy.Najbardziej rozpowszechnionym, formalnym systemem zapisu takich reguł (czyli zapisu gramatyki), w formie czytelnej dla człowieka jest postać BNF (Backus-Naur Form).Postać ta została opracowana przy pisaniu specyfikacji języka Algol 60.Podstawową jej cechą jest to, że każda gramatyka wyrażona w notacji BNF jest gramatyką bezkontekstową.Postać wejściową dla YACC'a stanowi gramatyka zapisana w notacji BNF w formacie czytelnym dla maszyny.Należy zaznaczyć, że nie wszystkie gramatyki bezkontekstowe mogą być przetworzone przez YACC'a.Podzbiór gramatyk, które mogą być przetworzone nazywa się LALR(1) i jest on podzbiorem zbioru gramatyk określanego jako LR(1).Definicja gramatyki LR(1) mówi, że jest to taka gramatyka, dla której w dowolnej chwili można określić, jak przetworzyć dany fragment tekstu wejściowego, odczytując tylko jeden symbol (jednostkę leksykalną) więcej, niż wymaga tego reguła.W języku angielskim tę jednostkę leksykalną określa się jako look-ahead token.Gramatyka LALR(1) jest gramatyką LR(1) z pewnymi małymi ograniczeniami, które w praktyce zdarzają się bardzo rzadko, a pozwoliły znacznie uprościć budowę generatora YACC.W formalnym zapisie gramatyki, każdą jednostkę syntaktyczną, lub ich grupą nazywa się symbolem.Jednostki, które składają się z grupy innych jednostek opisanych regułą gramatyczną, nazywamy symbolami nieterminalnymi.Natomiast jednostki niepodzielne nazywamy symbolami terminalnymi (są to jednostki leksykalne).Każdy symbol nieterminalny musi być opisany przez regułę gramatyczną określającą, jak można rozłożyć go na prostsze symbole.Dla przykładu jedną z reguł opisujących instrukcję języka C mógłby być opis instrukcji „return” zapisany jako ”instrukcja może składać się ze słowa kluczowego `return', `wyrażenia' i `średnika'”.Takich reguł opisujących instrukcję języka C byłoby znacznie więcej.Symbolami terminalnymi w tej regule są: słowo kluczowe `return' i średnik (`;').Natomiast symbol nieterminalny `wyrażenie' podlega dalszemu rozkładowi.W zapisie gramatyki wyróżniamy jeden symbol nieterminalny, który określa całość tekstu wejściowego w opisywanym języku.Jest on nazywany symbolem początkowym (ang.start symbol).W przypadku kompilatora ten symbol opisywałby cały program.Parser (analizator składniowy) wygenerowany przez YACC'a odczytuje sekwencję jednostek leksykalnych i grupuje te jednostki używając do tego reguł gramatycznych.Jeżeli wejście zawiera prawidłowy tekst (zapisany zgodnie z gramatyką danego języka), cała sekwencja jednostek leksykalnych zostanie zredukowana do jednego symbolu - symbolu początkowego.W przeciwnym razie parser zgłosi błąd składniowy.Reguły formalne w zapisie dla YACC'aGramatyka formalna jest konstrukcją matematyczną.Aby zdefiniować język dla YACC'a, należy stworzyć plik zawierający zapis gramatyki w formacie czytelnym dla YACC'a.Należy przy tym pamiętać o kilku zasadach.Symbol nieterminalny gramatyki formalnej jest w YACC'u reprezentowany przez identyfikator (wyraz złożony z liter, cyfr i znaku podkreślenia, w krórym pierwszy znak nie może być cyfrą) [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl centka.pev.pl
.Innym operatorem ułatwiającym konstrukcję wzorców jest operator opcjonalności - znak `?'.Ciąg w? oznacza ciąg w lub ciąg pusty.Możemy również używać symbolu `+', różniącego się od `*' tym, że nie zawiera ciągu pustego.Wzorzec m+ możemy więc zapisać jako m*m.Możemy również określić wprost krotność konkatenacji danego wyrażenia.Krotność tę zapisuje się po danym wyrażeniu, ujętą w nawiasy klamrowe.Specyfikacja generatora Lex zawiera jeszcze operator kropki (`.'), który odpowiada dowolnemu, widzialnemu znakowi.Generator Lex ma wbudowany mechanizm retrakcji, dzięki czemu unika dopasowywania ciągu do wzorcu w sytuacji, w której dłuższy ciąg (rozpoczynający się od dotychczas przeczytanego) mógłby zostać dopasowany.W chwili, gdy ciąg na wejściu został kompletnie dopasowany do jakiegoś wzorca, a zasada najdłuższego dopasowania sugeruje kontynuację dopasowania do innego wzorca, Lex zapamiętuje pozycję w tekście wejściowym i wzorzec, do którego udało mu się już dopasować ciąg wejściowy, a następnie kontynuuje dopasowanie do dłuższego „wzorca” (wzorca, do którego dopasowane tekst będzie dłuższy).W przypadku, gdyby dopasowanie nie powiodło się, Lex wraca do ostatniego dopasowanego wzorca, wykonuję związaną z nim akcję i rozpoczyna analizę od miejsca, w którym zakończył się dopasowany ciąg.Z zaawansowanych technik, które Lex udostępnia użytkownikowi, należy jeszcze wymienić możliwość uwzględniania kontekstu - zarówno prawego, jak i lewego.Pozwala to rozstrzygać sytuacje, w których ten sam ciąg znaków może być różnie potraktowany, w zależności od kontekstu, w którym występuje.Uwzględnianie lewego kontekstu zrealizowano w Lexie za pomocą możliwości korzystania ze stanów początkowych, natomiast uwzględnianie prawego kontekstu za pomocą możliwości konstruowania reguł typu w/p - reguła taka oznacza, że ciąg wejściowy można dopasować do wzorca w tylko wtedy, gdy po tym ciągu występuje ciąg pasujący do p.lAnaliza składniowa - YacclJak wspomniano wcześniej, z analizatora składniowego wyodrębnia się osobny moduł, analizator leksykalny, do zbudowania którego może nam posłużyć Lex.Analizator składniowy jest wtedy modułem nadrzędnym dla analizatora leksykalnego - wykorzystuje wyniki jego pracy.Dobrym narzędziem pomocniczym, służącym do tworzenia analizatorów składniowych, jest YACC - podobnie jak Lex opracowany w amerykańskiej firmie AT&T.YACC może współpracować z Lexem w systemie pionowym (patrz p. IV.4.1).Połączone siły obu narzędzi mogą posłużyć do tworzenia różnorakich translatorów i interpreterów - począwszy od prostego kalkulatora, zakończywszy na kompilatorach skomplikowanych języków programowania.Język i gramatyka bezkontekstowaPierwszym warunkiem, jaki musi spełniać język, aby można było przetwarzać go za pomocą YACCa jest bezkontekstowość jego gramatyki.Oznacza to, że opisując gramatykę języka, specyfikujemy jedną, lub więcej grup syntaktycznych i tworzymy (opisujemy) reguły konstruowania ich z części.Dla przykładu - w języku C taką grupą jest wyrażenie.Jedną z reguł tworzących wyrażenie może być zdanie: „wyrażenie składa się ze znaku minus i innego wyrażenia”.Inną może być zdanie: „wyrażenie może być liczbą całkowitą”.Jak widać, w opisie reguł często stosuje się rekursję, jednak musi istnieć przynajmniej jedna reguła, który rekursję kończy.Najbardziej rozpowszechnionym, formalnym systemem zapisu takich reguł (czyli zapisu gramatyki), w formie czytelnej dla człowieka jest postać BNF (Backus-Naur Form).Postać ta została opracowana przy pisaniu specyfikacji języka Algol 60.Podstawową jej cechą jest to, że każda gramatyka wyrażona w notacji BNF jest gramatyką bezkontekstową.Postać wejściową dla YACC'a stanowi gramatyka zapisana w notacji BNF w formacie czytelnym dla maszyny.Należy zaznaczyć, że nie wszystkie gramatyki bezkontekstowe mogą być przetworzone przez YACC'a.Podzbiór gramatyk, które mogą być przetworzone nazywa się LALR(1) i jest on podzbiorem zbioru gramatyk określanego jako LR(1).Definicja gramatyki LR(1) mówi, że jest to taka gramatyka, dla której w dowolnej chwili można określić, jak przetworzyć dany fragment tekstu wejściowego, odczytując tylko jeden symbol (jednostkę leksykalną) więcej, niż wymaga tego reguła.W języku angielskim tę jednostkę leksykalną określa się jako look-ahead token.Gramatyka LALR(1) jest gramatyką LR(1) z pewnymi małymi ograniczeniami, które w praktyce zdarzają się bardzo rzadko, a pozwoliły znacznie uprościć budowę generatora YACC.W formalnym zapisie gramatyki, każdą jednostkę syntaktyczną, lub ich grupą nazywa się symbolem.Jednostki, które składają się z grupy innych jednostek opisanych regułą gramatyczną, nazywamy symbolami nieterminalnymi.Natomiast jednostki niepodzielne nazywamy symbolami terminalnymi (są to jednostki leksykalne).Każdy symbol nieterminalny musi być opisany przez regułę gramatyczną określającą, jak można rozłożyć go na prostsze symbole.Dla przykładu jedną z reguł opisujących instrukcję języka C mógłby być opis instrukcji „return” zapisany jako ”instrukcja może składać się ze słowa kluczowego `return', `wyrażenia' i `średnika'”.Takich reguł opisujących instrukcję języka C byłoby znacznie więcej.Symbolami terminalnymi w tej regule są: słowo kluczowe `return' i średnik (`;').Natomiast symbol nieterminalny `wyrażenie' podlega dalszemu rozkładowi.W zapisie gramatyki wyróżniamy jeden symbol nieterminalny, który określa całość tekstu wejściowego w opisywanym języku.Jest on nazywany symbolem początkowym (ang.start symbol).W przypadku kompilatora ten symbol opisywałby cały program.Parser (analizator składniowy) wygenerowany przez YACC'a odczytuje sekwencję jednostek leksykalnych i grupuje te jednostki używając do tego reguł gramatycznych.Jeżeli wejście zawiera prawidłowy tekst (zapisany zgodnie z gramatyką danego języka), cała sekwencja jednostek leksykalnych zostanie zredukowana do jednego symbolu - symbolu początkowego.W przeciwnym razie parser zgłosi błąd składniowy.Reguły formalne w zapisie dla YACC'aGramatyka formalna jest konstrukcją matematyczną.Aby zdefiniować język dla YACC'a, należy stworzyć plik zawierający zapis gramatyki w formacie czytelnym dla YACC'a.Należy przy tym pamiętać o kilku zasadach.Symbol nieterminalny gramatyki formalnej jest w YACC'u reprezentowany przez identyfikator (wyraz złożony z liter, cyfr i znaku podkreślenia, w krórym pierwszy znak nie może być cyfrą) [ Pobierz całość w formacie PDF ]