1 Lingwistyka Matematycznawykład 5

2 Rozszerzenia notacji BNF Diagramy składniowe Agenda Rozszerzenia notacji BNF Diagramy składniowe Zamiana diagramów składniowych na kod analizatora Podsumowanie Q&A Mgr inż. Michał Jaros

3 Metody zapisu gramatykGramatyka Pāņini’ego Notacja BNF i jej rozszerzenia Notacja WSN Diagramy składniowe Mgr inż. Michał Jaros

4 Ashtadhyayi („Ośmioksiąg”) Gramatyka sanskrytu Gramatyka Pāņini’ego Autor Pāņini Powstał w V w.p.n.e. Ashtadhyayi („Ośmioksiąg”) Gramatyka sanskrytu 3959 reguł gramatycznych Mgr inż. Michał Jaros

5 Backus–Naur form (BNF)Notacja BNF Backus–Naur form (BNF) Metasymbole notacji BNF: <, >, ::=, | ::= | ::= "<" ">" "::=" ::= | "|" ::= | ::= | "<" ">" ::= """ """ ::= ::= kwiaty | gwiazdy ::= kwitną | świecą Mgr inż. Michał Jaros

6 Wirth syntax notation (WSN)Notacja WSN Wirth syntax notation (WSN) SKŁADNIA = { PRODUKCJA } . PRODUKCJA = IDENTYFIKATOR "=" WYRAŻENIE "." . WYRAŻENIE = SKŁADNIK { "|" SKŁADNIK} . SKŁADNIK = CZYNNIK { CZYNNIK } . CZYNNIK = IDENTYFIKATOR | LITERAŁ | "(" WYRAŻENIE ")" | "[" WYRAŻENIE "]" | "{" WYRAŻENIE "}" . IDENTYFIKATOR = litera { litera } . LITERAŁ = """ znak { znak } """ . Mgr inż. Michał Jaros

7 Rozszerzenia notacji BNF (EBNF)Extended Backus–Naur form (EBNF) Zapis w BNF Zapis w EBNF Znaczenie ::= jest zdefiniowany przez | lub zakończenie formuły brak { x } 0 lub wielokrotne powtórzenie symbolu x symbol nie terminalny symbol symbol terminalny Mgr inż. Michał Jaros

8 Rozszerzenia notacji BNF (MBNF)Modified Backus–Naur form (MBNF) Zapis w EBNF Zapis w MBNF Znaczenie ::= = jest zdefiniowany przez | lub . zakończenie formuły brak [ x ] 0 lub jednokrotne powtórzenie symbolu x { x } 0 lub wielokrotne powtórzenie symbolu x ( x | y | … | z ) dowolny z symboli x, y, … , z symbol-nie-term symbol nie terminalny symbol "symbol" symbol terminalny Mgr inż. Michał Jaros

9 Diagram składni (diagram kolejowy)Diagramy składniowe Diagram składni (diagram kolejowy) Sposób prezentacji gramatyk formalnych Graficzna alternatywa dla BNF i innych Przejrzysty obraz struktury języka Bardziej czytelne dla człowieka Mniej czytelne dla komputera Dobry przy projektowaniu języka Mgr inż. Michał Jaros

10 Fragment diagramu składni JSON’aDiagramy kolejowe ? Fragment diagramu składni JSON’a Mgr inż. Michał Jaros

11 Diagramy składniowe - reguły konstrukcjiA=B. A="x". Mgr inż. Michał Jaros

12 Diagramy składniowe - reguły konstrukcjiA= α1 α2 … αn. Mgr inż. Michał Jaros

13 Diagramy składniowe - reguły konstrukcjiA="α1" | "α2" | … | "αn". Mgr inż. Michał Jaros

14 Diagramy składniowe - reguły konstrukcjiA= ["x"]. Mgr inż. Michał Jaros

15 Diagramy składniowe - reguły konstrukcjiA= {"x"}. Mgr inż. Michał Jaros

16 Zamiana diagramów składniowych na kod analizatoraDiagram składniowy ≈ schemat blokowy analizatora Reguły przejścia od diagramu do kodu analizatora Cel działania analizatora: Sprawdzenie poprawności składniowej Wygenerowanie komunikatów o błędach Mgr inż. Michał Jaros

17 Zamiana diagramów składniowych na kod analizatoraprocedure A; begin … end; Mgr inż. Michał Jaros

18 Zamiana diagramów składniowych na kod analizatora… if ch = "x" then read(ch) else błąd; … if ch in pierw(B) then B() else błąd; Mgr inż. Michał Jaros

19 Zamiana diagramów składniowych na kod analizatora… case ch of "x" : read(ch); "y" : read(ch); "z" : read(ch); else błąd; end; Mgr inż. Michał Jaros

20 Zamiana diagramów składniowych na kod analizatora… while ch = "x" do read(ch); Mgr inż. Michał Jaros

21 Rozszerzenia notacji BNF Diagramy składniowe Podsumowanie Rozszerzenia notacji BNF Diagramy składniowe Analizator składniowy z diagramu składni Mgr inż. Michał Jaros

22 Q&A Mgr inż. Michał Jaros

23 KONIEC Mgr inż. Michał Jaros