Este posibil să convertiți gramatica ANTLR3 în expresie regulată?

Am un parser gramatical simplu ANTLR3 care preia linii scurte de text și le convertește în obiecte Java. În continuare, am o listă mare de linii de text. Unele dintre ele (mai puțin de 1%) pot fi convertite deoarece se potrivesc cu gramatica.

Trebuie să le trec pe toate prin parser pentru a înțelege care sunt convertibile și pentru a crea o colecție de obiecte Java. Operație foarte consumatoare de timp. Ar fi mult mai eficient să le treceți printr-o expresie regulată înainte de a le trimite la ANTLR3.

Pot să creez eu un astfel de regex, dar ar fi mult mai bine să-l obțin dinamic de la analizatorul ANTLR3. Se poate face?


java antlr antlr3
person yegor256    schedule 15.03.2011    source sursă
comment
Oarecum fără legătură, dar dacă există o relație strictă de o linie-un obiect, puteți paraleliza cu ușurință procesarea.   -  person biziclop    schedule 16.03.2011

Răspunsuri (2)


arrow_upward
4
arrow_downward

În general, numai limbajele regulate pot avea o expresie regulată care le descrie. (Majoritatea motoarelor RE acceptă funcții care se potrivesc și cu unele limbi neobișnuite (de exemplu, prin referințe din spate), dar nu toate limbajele fără context sau chiar formale generale.)

Nu sunt cu adevărat un expert în antlr, dar presupun că gramaticile sale se pot potrivi cu limbi care nu sunt re-potrivibile.

Deci, nici rezolvabilitatea teoretică a problemei tale nu este cu adevărat dată, depinde de gramatică.

Poate că

  • gramatica ta este de fapt o gramatică obișnuită, sau
  • că există un limbaj obișnuit care este un ușor supraset al limbajului gramatical - astfel RE poate filtra majoritatea liniilor care nu se potrivesc, în timp ce unele vor fi filtrate doar de gramatică/parser.

Cel mai probabil, nu există o modalitate sigură de a fi sigur fără a vă vedea gramatica.

De asemenea, o expresie regulată nu este neapărat mai rapidă decât ar fi analizatorul dumneavoastră.

person Paŭlo Ebermann    schedule 15.03.2011
comment
+1 pentru teoria limbajului și pentru observația că ar putea exista un limbaj obișnuit care este un ușor supraset al unui anumit limbaj neregulat - nu m-am gândit la asta înainte. - person Aasmund Eldhuset; 16.03.2011

arrow_upward
1
arrow_downward

Pentru a fi specific despre ANTLR, poate analiza LL(*) subclasa gramatici fără context.

Pentru a afla dacă limba dvs. este obișnuită, vedeți dacă puteți aplica lema de pompare pentru limbile obișnuite.

person Matthew Sowders    schedule 15.03.2011