• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Gramatyka formalna



    Podstrony: 1 [2] [3]
    Przeczytaj także...
    Analizator składniowy lub parser – program dokonujący analizy składniowej danych wejściowych w celu określenia ich struktury gramatycznej w związku z określoną gramatyką formalną. Nazwa analizator składniowy podkreśla analogię z analizą składniową stosowaną w gramatyce i językoznawstwie. Analizator składniowy umożliwia przetworzenie tekstu czytelnego dla człowieka w strukturę danych przydatną dla oprogramowania komputera.Gramatyka kombinatoryczna – gramatyka formalna bez ograniczeń na postać reguł. W hierarchii Chomsky’ego jest to gramatyka typu 0. Generuje język rekurencyjnie przeliczalny.

    Gramatyka formalna – sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.

    Do zdefiniowania gramatyki formalnej potrzebne jest określenie zbioru symboli terminalnych, zbioru symboli nieterminalnych, symbolu startowego oraz zbioru reguł określających sposób wyprowadzania słów.

    Symbol nieterminalny to symbol, który można definiować. Symbole nieterminalne zwane są również zmiennymi syntaktycznymi, ponieważ umożliwiają tworzenie ciągów zawierających kombinacje symboli terminalnych i nieterminalnych.

    Modelowanie matematyczne to użycie języka matematyki do opisania zachowania jakiegoś układu (na przykład układu automatyki, biologicznego, ekonomicznego, elektrycznego, mechanicznego, termodynamicznego).Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.

    Symbol terminalny to symbol elementarny tworzący wyrazy języka formalnego. Symbole terminalne są znakami, które mogą pojawić się na wejściu lub wyjściu z reguł produkcji gramatyki formalnej. Symbol terminalny nie może być podzielony na „mniejsze” jednostki, lub ściślej: symbole terminalne nie mogą być zmieniane za pomocą reguł gramatyki formalnej, w odróżnieniu od symboli nieterminalnych.

    Symbol startowy to symbol nieterminalny wyróżniony w konkretnej gramatyce formalnej, taki że generację słowa w tej gramatyce zaczynamy od słowa złożonego z tego symbolu.Postać normalna Chomsky’ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci:

    Gramatyka formalna posiada wyróżniony symbol nieterminalny, zwany symbolem startowym, od którego, poprzez stosowanie reguł produkcji, zaczyna się wyprowadzanie wszystkich wyrazów języka formalnego. Tworzenie wyrazu języka formalnego kończy się wówczas gdy zawiera on już tylko symbole terminalne.

    Symbole terminalne (równoważne symbolom alfabetu języka) są symbolami, które pozostaną w wyprowadzonym słowie – w przeciwieństwie do symboli nieterminalnych używanych tylko podczas wyprowadzania słowa. Reguły gramatyki postaci gdzie i to ciągi symboli terminalnych i nieterminalnych, określają możliwe podstawienia symboli w wyprowadzanym słowie. Wyprowadzanie rozpoczynamy od ciągu złożonego z wyróżnionego symbolu nazywanego symbolem początkowym. Odbywa się ono przez zastępowanie podciągów tego ciągu zgodnie z regułami gramatyki. Jeśli w ciągu mamy podciąg możemy zastąpić go przez

    Gemeinsame Normdatei (GND) – kartoteka wzorcowa, stanowiąca element centralnego katalogu Niemieckiej Biblioteki Narodowej (DNB), utrzymywanego wspólnie przez niemieckie i austriackie sieci biblioteczne.

    Rozważmy przykładową gramatykę z symbolem nieterminalnym S, który jest jednocześnie symbolem startowym, oraz zbiorem symboli terminalnych Reguły tej gramatyki, która umożliwia generowanie słów postaci ba, abab, aababb, aaababbb itd. wyglądają następująco:

  • Zaczynamy od symbolu startowego S, możemy zastąpić go przez aSb zgodnie z pierwszą regułą. Możemy użyć jej jeszcze raz otrzymując aaSbb. Po użyciu drugiej reguły pozostanie nam ciąg aababb. Składa się on tylko z symboli terminalnych, więc wyprowadzenie słowa zostało zakończone.

    Symbol startowy[ | edytuj kod]

    Wymaganie, żeby symbol startowy był jeden, nie ogranicza nam szczególnie możliwości budowania gramatyk. Jeśli chcemy zacząć generację od jakiegoś innego słowa lub od pewnych kilku możliwych słów możemy dodać symbol „przedstartowy” oraz reguły postaci będące sumarycznie podzbiorem wszystkich dozwolonych reguł dla danej gramatyki. Wystarcza nam więc jeden symbol startowy, niezależnie od tego, od ilu możliwych słów zamierzamy zaczynać.

    Podstrony: 1 [2] [3]




    Reklama

    Czas generowania strony: 0.016 sek.