i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 > 100). evaluation part seems to be easy as i will convert infix to postfix and evaluate postfix without 'paren()'.

i am not fully sure which method should i be using.

can any one point me to a book with algorithm or a link.

  • 6
    $\begingroup$ Take a look at context-free grammars and some parsing algorithms $\endgroup$ – skankhunt42 Nov 16 '16 at 7:02
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 3 '16 at 11:26

What you are describing is part of the area of knowledge known as compiler theory, specifically parsing. One of the classical books is the dragon book. Parsing and evaluating expressions like yours is usually done in three interlocked steps:

  1. Lexical analysis. This part is in charge of converting the input into a sequence of "lexemes". It will convert your example into the lexemes "(" VARIABLE "=" NUMBER ")" "or" "(" VARIABLE ">" NUMBER ")". This step is implemented using regular automata.

  2. Syntax analysis. This part construct a parse tree of your expression. In your case, the parse tree (generated using Miles Shang's online tool) will be: Parse tree This step is implemented using context-free languages, either using a table-based approach or using recursive descent.

  3. Semantic analysis. In your case, this part will evaluate the expression recursively using the parse tree, making use of attributes stored at the meta-lexemes VARIABLE and NUMBER.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.