Context free grammar, czy ten przykład do tego należy

0

Przykładowy język i parser do niego. Język składa się z obiektów i operatorów. Operatory to albo plus (dodawanie) albo znak równości.
Przykładowo: obj1 + obj2 = obj3
Każdy z obietków to seria podobiektów: obj -> subobj obj | subobj
Każdy z podobiektów może być podpodobiektem lub podpodobiektem zamkniętym w nawiasach: subobj -> subsubobj | (subsubobj)
Podpodobiekt może być również plusem (może zawierać znak plus i inne znaki), ale wtedy nie oznacza dodawania, tylko co innego.
Czy jest to context free grammar i ewentualnie jak ją formalnie zapisać?
Przykładowo: (a+)b + a = a+b, tylko pierwszy plus nie jest dodawaniem, reszta oznacza dodawanie.

0

A takie coś mogło by być: a++b = c ? Bo jeśli tak to odpowiedź brzmi: nie, bo widać juz na oko że nie parsuje się to jednoznacznie.

0

Zobaczymy czy z tego się da stworzyć context free grammar, ale tak jak ją Opisałeś, to nie bardzo (na przykład co znaczy ta linijka: obj -> subobj obj | subobj).
Ja bym to ułożył tak:
object -> subobject | object
grupa -> "("object")" //z tego wynika, że subbject może być w nawiasach, jak również object.
unarny -> ("+" | "#") object
operator -> "+" | "="
binary -> object operator object

Trochę dziwna ta gramatyka, ale jakoś tam się to chyba trzyma kupy:
(a + b) + +c = a, na przykład.

Widze, że @Shalom dodał uwagę, wydaje mi sie, że tak jak to opisałem to sytuacja z tej uwagi nie zachodzi...
Edit: Trochę wyjaśnień: Moje dwie pierwsze linijki mówia to samo co Twoje: obj -> subobj obj | subobj i subobj -> subsubobj | (subsubobj) - zwierają logicznie to samo - chyba, że chodziło Ci o co innego, a ja nie załapałem (bardzo mozliwe:-))

0

Może trochę prościej, przykładowo takie coś jest poprawne: abcd(ab(a+)) + ab(+) = ab.
Zasadniczo literki sobie coś tam oznaczają (już bez wprowadzania podziału na grupy i podgrupy), natomiast plus oznacza coś innego niż dodawanie, jeżeli jest wewnątrz pary nawiasów. Oczywiście nawiasy muszą być sparowane i poprawnie ułożone. Jeżeli plus jest poza nawiasami, oznacza dodawanie.
Odnośnie znaku równości, to chyba niezbyt ważne teraz, czy oznacza on przypisanie czy porównanie, ale jednak oznacza on porównanie.
@Shalom takie coś mogłoby być dla uproszczenia (syntactic sugar), ale na razie przyjmijmy, że nie trzeba tego obsługiwać i że nie musi to być rozpoznawane, wtedy może być możliwość na context free grammar

Zaproponowana powyżej gramatyka chyba nie bardzo pasuje, bo nie ma w niej plusa zawartego w obiekcie.

Podpodobiekt może być również plusem (może zawierać znak plus i inne znaki), ale wtedy nie oznacza dodawania, tylko co innego.

Btw, polecacie może jakieś źródła odnośnie języków, gramatyk i parsowania? Na pewno są jakieś grube pozycje, a macie coś na wstęp, co można przelecieć w kilka, kilkanaście godzin? Dzięki za odpowiedzi

0

Zajrzyj tutaj: https://www.springer.com/us/book/9780387202488, nie Musisz czytać całości, i tutaj: http://craftinginterpreters.com/ .
Co do Twojego języka, to to co Podałeś, nie mieści się w tej gramatyce: abcd(ab(a+)) jaka jest tego semantyka, czy to jest funkcja? Gdzie są reguły produkcji dla (a+) , ab(+)?

0

Znaczenie tych nawiasów jest takie, że są to oddzielone grupy obiektów, które jednak przynależą do jakiegoś nadobiektu. Taki sposób na pogrupowanie ich po prostu, nawiasy nie oznaczają raczej wywołań funkcji. Reguły są takie, że:
subobject -> subsubobject | (subsubobject), a subsubobject -> /[a-z]/ | /[a-z]/ subsubobject | +. Mniej więcej tak.
Btw, czy kolejność podawania reguł ma znacznie i czy kolejność podawania alternatyw w ramach jednej reguły ma jakieś znacznie?
Czy skoro plus w ramach nawiasów ma inne znaczenie niż na zewnątrz, czy może być to nadal context free grammar.

0

Ano może, bo możesz podać różne reguły produkcji dla obydwu, dbając, żeby były jednoznaczne:
object -> subobject | unary | binary
unary -> ("+" | "-") object
binary -> object operator object
operator -> "=" | "+" // i może jeszcze jakieś
Te: subobject -> subsubobject | (subsubobject), a subsubobject -> /[a-z]/ | /[a-z]/ subsubobject | +
produckcje tutaj Podałeś jakieś bardzo dziwne, nie wiem czy to się da jakoś jednoznacznie sparsować. Naprawdę nie wiem co Chcesz, jaka ma być semantyka tej gramatyki? To trzeba bardzo dokładnie planowac, żeby nie było wieloznaczności...

0

Może dla jasności, przykład, który dokładniej wyjaśni sprawę, a jednocześnie jest bardzo znany i podobny do oryginalnej kwestii.
Równania reakcji chemicznych, przykładowo H2+O2=H2O. Tutaj jest sprawa jasna, plus oznacza dodawanie. Teraz H3O(+)+O2=H(+) + H2O, w tym wypadku plus w nawiasie oznacza ładunek dodatni, a nie dodawanie. Ewentualnie (H3O+)+O2 = H(+) + H2O, cała molekuła może być w nawiasie.
Kwestia następująca, czy pomimo iż plus jest różnie traktowany w zależności od tego, czy jest w nawiasach, czy nadal może to być context-free grammar.
Przykładowo:

number -> /\d+/
element -> /[A-Z][a-z]*/
pair -> element number? | + number?
group -> (pair*) number?
molecule -> pair | group | pair molecule | group molecule
equation -> molecule (+ molecule)* = molecule (+ molecule)*

Ale mimo ułożenia takiej gramatyki, takie coś nadal jest poprawne H3O(+) + O2++ = H(+) + H2O.
Jak ułożyć tę gramatykę? Jak to formalnie zapisać.
Jeszcze pytanie na boku, w momencie w którym znak plus oznacza 2 różne node'y, kiedy się tym zająć? W lexerze zwrócić token typu T_PLUS i zająć się semantyką w parserze, czy od razu zwracać T_OPERATOR_PLUS albo T_CHARGE_PLUS i parsować bezpośrednio w parserze.

0

Przygotowaniem poprawnej struktury, musi sie zajac tokenizer; zeby O2++ nie wyszlo jako token do parsera. Mysle, ze plus Moze byc jeden, jak to bedzie poprawnie stokenizowane, to parser sobie poradzi.

0

Ale to nie jest dokładna gramatyka dla zapisu tych chemicznych reakcji. Jak skonstruować taką poprawną?
Poza tym, gdyby odróżnić plus jako non-terminal symbol z podziałem, na przykład:

number -> /\d+/
element -> /[A-Z][a-z]*/
plus_charge -> + (co tu wpisać dla odróżnienia)
plus_operator -> +  (co tu wpisać dla odróżnienia)
pair -> element number? | plus_charge number?
group -> (pair*) number?
molecule -> pair | group | pair molecule | group molecule
equation -> molecule (plus_operator molecule)* = molecule (plus_operator molecule)*

Jak to formalnie zapisać w context-free grammar.

0

Nie wiem w tej chwili jak z tego stworzyć gramatykę context free, ale można to zrobić prościej: Ładunek oznaczać HO[+], plus będzie normalnym operatorem binarnym, nawiasy, jak w wyrażeniu arytmetycznym i pozamiatane.

1 użytkowników online, w tym zalogowanych: 0, gości: 1