Parser schreiben

Sonstiges Theoretisches
1

Hallo,
Ich habe eine Frage zum Parser schreiben. So weit ich weiß gibt es einen Tokenizer und ein Parser der die Tokens in ein Syntaxbaum einfügt. Um das besser zu verstehen habe ich mir ein minimales Markup ausgedacht, der in HTML-Code verwandelt wird.

[ol]
[li]Fall **fett** soll ergeben: <strong>fett</strong>
[/li][li]Fall //kursiv// soll ergeben: <em>kursiv</em>
[/li][li]Fall **//fett kursiv//** soll ergeben: <strong><em>fett kursiv</em></strong>
[/li][/ol]

Der 3. Fall kann leicht zu invaliden HTML-Code führen. Beispielhaft gibt sich dieser Fehlerfall:**//Fehler**, denn ich möchte, dass es folgendes ergibt <strong>//Fehler</strong> und nicht <strong><em>Fehler</strong>

Lösung 1

Ich gliedern die Tokens in BOLD_START und BOLD_END, sowie ITALIC_START und ITALIC_END. Der Tokenizer müsste schon den nächsten Token erkennen nachdem er diesen einliest, damit man sicher sein kann das es ein Ende gibt. Bei dieser Lösung zu bemerken ist, dass der Tokenizer den nächsten gleichen Token wissen müsste um die Richtigkeit des jetzigen zu bestätigen.

Lösung 2

Ich gliedern die Tokens in BOLD und ITALIC. Der Parser müsste in dem Fall erkennen ob es sich bei diesen BOLD oder ITALIC sich um ein Ende oder ein Anfang handelt und es dann passend im Syntaxbaum einfügen. Bei dieser Lösung zu bemerken ist, dass auch falsche Tokens auch zum Parser kommen können und der Parser entsprechend behandeln müsste.

Mein Problem ist, dass ich nicht weiß welcher der Lösungen optimaler ist.
Grüße,
MDickie

2

Verwende MarkDown. Ist recht einfach, gut verständlich und weit verbreitet (GitHub, StackOverflow , …).
Dürft da sicher für alle Sprachen schon Libs geben.

3

Nö, das ist für Tabellen ungeeignet. WikiCreole scheint eine bessere Wahl zu sein. Jedoch scheint es keinen ordentlichen Parser für Python zu geben (sprich ohne RegEX).

4

Gitbub Flavored Markdown schon, dürfte es auch Parser dafür geben.

5

Beantwortet nicht meine eigentliche Frage, da ich gerne ein Review beider Lösungen gehabt hätte. Mittlerweile finde ich, dass die erste Lösung besser ist. Der Tokenizer wird aber nicht überprüfen ob ein Ende vorhanden ist, sondern der Parser wird überprüfen ob ein Ende existiert und abhängig davon wird er entscheiden wie es geparst wird.
Grüße,
MDickie

6

Lösung 1 wird so in keinem Tokenizer verwendet, denn das Start-Symbol ist ja das selbe wie das Ende-Symbol. Und der Tokenizer kennt nur Tokens und keine Grammatik, kann also nicht Anfang und Ende unterscheiden.
Wenn dann Lösung 2, so macht es jeder andere generierte Parser auch.

7

Keine deiner Lösungen ist optimal. Normalerweise würdest du einen Token anlegen für bold, italic und bold-italic. Der kann natürlich aus Start und Anfang bestehen, das ist allerdings nur für den Lexer interessant. Für den Parser ist nur der Text-Token interessant. Wie sieht denn deine Grammatik aus und welches Tool verwendest du? Ich persönlich hab’ mir nur mal xText kurz angesehen und mit Yacc und Antlr tatsächlich ein bisschen was gemacht. Meine Empfehlung ist Antlr. Siehe auch diesen Thread für ein minimal Beispiel. Da hab ich sogar mit der komplexen C-Grammatik schnell einen Parser gebastelt: Möglicht C Code zu parsen.

8

Für bold-italic würde ich keinen eigenen Token anlegen, wozu auch.

9

Das kommt auf deine Grammatik an. Du kannst das entweder als 3 verschiedene Ausdrücke anlegen oder als zwei wovon eines Schachtelhalm ist. Oder programmierst du alles zu Fuß und hast gar kein Grammatik-File?

10

Für die einfache Grammatik geht das ja noch ohne Parser. Aber ich würde in so einem Fall nie bold-italic als ein Token machen, denn dann bräuchte man ja auch ein italic-bold wenn es umgedreht kommt. Und dann kommt noch ein Unterline irgendwann dazu, und ein Strikeout, und dann davon alle Permutationen als Token? Die einzelnen Tokens verschachtelt decken ja schon alles ab. Richtig schlimm wirds dann wenn du als Sequenz „bold-italic text italic text bold bekommst“. Verschachtelt kein Problem. Keep it simple :wink:
Aber du hast natürlich recht, es hängt stark von der Grammatik ab was wirklich sinnvoller ist. Aber ich habe schon so viele Parser geschrieben/generiert, da sagt die Erfahrung dass es einfacher ist das zu verschachteln.

11

Hallo,
Ja, Ich bin auch für KISS. Ich habe entschieden, dass ich es mit PLY machen werde und habe bisschen Code niedergeschrieben. Nur weiß ich jetzt nicht wie ich Elemente verschachtle. Vielleicht könnt ihr mir helfen.
[PYTHON]tokens = (
‘BOLD’,‘ITALIC’, ‘TEXT’
)

Tokens

t_BOLD = r’**’
t_ITALIC = r’//’
t_TEXT = r’[A-Za-z0-9_ ////][A-Za-z0-9_ !.////]*’

Ignored characters

t_ignore = " "

def t_newline(t):
r’
+’
t.lexer.lineno += t.value.count("
")

def t_error(t):
print(“Illegal character ‘%s’” % t.value[0])
t.lexer.skip(1)

Build the lexer

import ply.lex as lex
lex.lex()

Parsing rules

precedence = (
(‘left’,‘BOLD’,‘ITALIC’),
)

def p_statement_expr(t):
‘statement : expression’
print(t[1])

def p_expression_bold(t):
‘expression : BOLD TEXT BOLD’
if t[1] == ‘**’: t[0] = “” + t[2] + “”

def p_expression_italic(t):
‘expression : ITALIC TEXT ITALIC’
if t[1] == ‘//’: t[0] = “” + t[2] + “”

def p_error(t):
print(“Syntax error at ‘%s’” % t.value)

import ply.yacc as yacc
yacc.yacc()

while 1:
try:
s = raw_input('calc >
') # Use raw_input on Python 2
except EOFError:
break
yacc.parse(s)
[/PYTHON]
Grüße,
MDickie

12

Ja, da hast du recht. Stimmt schon wie du es sagst.

Mir kommt deine Grammatik ein wenig arg simpel vor. Normalerweise würdest du noch einen zusätzlichen Ausdruck einführen, der die zwei Schachtelmöglichkeiten enthält. Ich kenne mich mit PLY nicht aus, aber so wie da der Code aussieht geht das gar nicht, oder?.

Ich würde eine Expression definieren die dir die Möglichkeiten zusammenfasst:


simple
  : BoldExp
  | ItalicExp 
  ;

encapsulated
  : BOLD simple BOLD
  | ITALIC simple ITALIC
  ;

Wenn dein Parser-Generator Rekursion zulässt, könntest du das ganze sogar rekursiv machen. Je nach dem ob du das brauchst. So in etwa:


SimpleExp
  : BoldExp
  | ItalicExp
  ;

MarkupExp
  : SimpleExp
  | BOLD MarkupExp BOLD
  | ITALIC MarkupExp ITALIC
  ;

Und dann fügst du außen nur ** oder // an und im Falle von SimpleExp greift die andere Regel.

13

ich kenne jetzt keine vereinfachten Tools, aber wenn hätte ich einfach etwas mit cup und jlex gebaut, ist etwas aufwändiger aber man kann alles bauen was man will

14

Danke alle meine Fragen sind beantwortet.