postfix parser

[Leonhard]

Endlich geschafft. Ich möchte hier meinen Postfix-Parser vorstellen (der code ist nen bischen undurchsichtig, aber wer was über Postfix-Parser weis, sollte durchschauen).

Ich hab seit 1-2 Jahren mich mit so nem Parser beschäftigt, doch es nie richtig hinbekommen.

Ach ja, wer sich noch über Postfix-Parser informieren will:
http://informatik.unibas.ch/lehre/ss07/ ... 09-2up.pdf
http://de.wikipedia.org/wiki/Compiler

Code: Alles auswählen

;/ infix
;a + b * c + (d * e + f) * g
;a + b * c + d * e + f * g

;/ postfix
;a b c * + d e * f + g * +
;a b c * + d e * + f g * +

EnableExplicit

Define Infix.s = "a+b*c+(d*e+f)*g"

Define s.s{1}

Macro m_IsOperand
  s = "a" Or s = "b" Or s = "c" Or s = "d" Or s = "e" Or s = "f" Or s = "g"
EndMacro
Macro m_IsOperator
  s = "+" Or s = "*"
EndMacro

Define operand_left.s{1}
Define operand_right.s{1}
Define operator.s{1}
Define diference.l
Define ToOperatorStack.b

Procedure.l GetOperatorPriority(operator.s)
  Select operator
  Case "+" : ProcedureReturn 1
  Case "*" : ProcedureReturn 2
  EndSelect
EndProcedure

Structure Stack
  clip_level.l
  
  s.s{1}
EndStructure
NewList Stack.s{1}() ; Initialisiere Stack
NewList OperatorStack.Stack()
NewList Output.s{1}()
Define n.l, clip_level.l
For n = 1 To Len(Infix); DO Lese Postfix-Ausdruck Symbol für Symbol
  s = Mid(Infix, n, 1)
  Debug s
  If m_IsOperand ;IF nächstes Symbol ein Operand THEN
    AddElement(Stack()) : Stack() = s ;push Operand
  ElseIf s = "("
    clip_level + 1
    Debug "CKIP +1"
  ElseIf s = ")"
    clip_level - 1
    Debug "CKIP -1"
  ElseIf m_IsOperator ;IF nächstes Symbol ein Operator THEN
    Debug "OP--------"
    If CountList(Stack()) <> 0
      operand_left = Stack() : DeleteElement(Stack(), #True)
      
      AddElement(Output()) : Output() = operand_left
    Else
      operand_left = ""
    EndIf
    
    operator = s
    
    ToOperatorStack = #True
    s = Mid(Infix, n+1, 1)
    If m_IsOperand
      n + 1
      ToOperatorStack = #False
      operand_right = s
      AddElement(Output()) : Output() = operand_right
    EndIf
    
    diference = 0
    s = Mid(Infix, n+1, 1)
    If ToOperatorStack Or ( (m_IsOperator) And GetOperatorPriority(operator) < GetOperatorPriority(s) )
      AddElement(OperatorStack()) : OperatorStack()\s = operator : OperatorStack()\clip_level = clip_level
      diference + 1
    Else
      AddElement(Output()) : Output() = operator
    EndIf
    
    If CountList(OperatorStack())-diference
      SelectElement(OperatorStack(), CountList(OperatorStack())-1-diference)
      Repeat
        If OperatorStack()\clip_level = clip_level And (Not GetOperatorPriority(OperatorStack()\s) < GetOperatorPriority(s))
          Debug "AddOutputFromOp.Stack "+OperatorStack()\s+" "+Str(OperatorStack()\clip_level)+" = "+Str(clip_level)
          AddElement(Output()) : Output() = OperatorStack()\s
          DeleteElement(OperatorStack(), #True)
        Else
          Break
        EndIf
      Until PreviousElement(OperatorStack()) = 0
    EndIf
  EndIf;FI
Next ;OD

Debug "RESULT ---------------------------"

;Schlussresultat auf dem Stack
ForEach Output()
  Debug Output()
Next

Verbesserungsvorschläge sind herzlich willkommen. Wer lust hat, den Code schönder zu schreiben (und zu kommentieren) wird herzlich dazu "eingelanden"

[Spirit]

Ich habe das mal als Recursive Descent Parser umgesetzt. Der Code
macht im Prinzip auch nichts anderes als dein Code, dürfte sich aber
ein bisschen leichter erweitern lassen. Die Fehlerbehandlung ist zwar
nicht perfekt, aber in den meisten Fällen funktioniert sie.

Code: Alles auswählen

EnableExplicit

; Syntax in EBNF:
; Expression = Term { ['+' | '-'] Term }.
; Term = Factor { ['*' | '/'] Factor }.
; Factor = Operand | '(' Expression ')'.

Enumeration ; Symboltypen
  #Plus
  #Minus
  #Times
  #Slash
  #LParen
  #RParen
  #Operand
  #EndOfLine
EndEnumeration

Global NewList postfix.s{1}()

Global infix.s = "a + b * c + (d * e + f) * g"
Global symbol.s{1}
Global symbolType.l
Global cursorPos.l = 1

; Scanner

Procedure NextSymbol()
  While cursorPos <= Len(infix) And Mid(infix, cursorPos, 1) = " " ; Leerzeichen überspringen
    cursorPos + 1
  Wend
  
  If cursorPos > Len(infix)
    symbolType = #EndOfLine
    ProcedureReturn
  EndIf
  
  symbol = Mid(infix, cursorPos, 1)
  
  Select symbol
    Case "+": symbolType = #Plus
    Case "-": symbolType = #Minus
    Case "*": symbolType = #Times
    Case "/": symbolType = #Slash
    Case "(": symbolType = #LParen
    Case ")": symbolType = #RParen
    Default
      If Asc(symbol) >= 97 And Asc(symbol) <= 122
        symbolType = #Operand
      Else
        Debug "Ungültiges Zeichen: " + symbol
        End
      EndIf
  EndSelect
  
  cursorPos + 1
EndProcedure

; Parser

Macro Emit(op)
  AddElement(postfix())
  postfix() = op
EndMacro

Declare Expression()

Procedure Factor()
  If symbolType = #Operand
    Emit(symbol)
    NextSymbol()
  ElseIf symbolType = #LParen
    NextSymbol()
    Expression()
    
    If symbolType <> #RParen
      Debug ") erwartet an Position: " + Str(cursorPos - 1)
      End
    EndIf
    
    NextSymbol()
  Else
    Debug "Operand oder ( erwartet an Position: " + Str(cursorPos - 1)
    End
  EndIf
EndProcedure

Procedure Term()
  Define.s{1} op
  
  Factor()
  
  While symbolType = #Times Or symbolType = #Slash
    op = symbol
    
    NextSymbol()
    Factor()
    
    Emit(op)
  Wend
EndProcedure

Procedure Expression()
  Define.s op
  
  Term()
  
  While symbolType = #Plus Or symbolType = #Minus
    op = symbol
    
    NextSymbol()
    Term()
    
    Emit(op)
  Wend
EndProcedure

Procedure Parse()
  NextSymbol()
  Expression()
EndProcedure

; Test

Parse()

ForEach postfix()
  Debug postfix()
Next

[Leonhard]

Dein Beispiel ist gut, aber für meine verhältnisse etwas unpraktisch.

Ich habe nur bewusst mit Operatoren-Priotität gearbeitet, da ich es unsinn finde, das ganze mit bis zu 9 verschiedenen Prioritäten alles in eine Procedure zu fassen.

Ich weis, das es bei meinem Parser etwas schwer ist, Operatoren wie '=' und ! einzubauen, aber man hat, wenn man es geschaft hat, eine schöne, kleine Procedure, die alle expressions ausführen kann (und keinen haufen von vielen verschachtelten Proceduren).

Ist halt alles eine sache des Programmier-Styles.