Small Basic: Parser Generator

Small Basic: Parser Generator


Overview


This article introduces Parser and Parser Generator written in Small Basic.

What's a Parser?


Parser is a program which analyzes program language syntax and does something. That will be a compiler, an interpreter, a program formatter, a program converter, or etc.

For example, calculator accepts expressions for it's input.  The expression will be analyzed as follows.  That is parsing. 

Expression has it's syntax as following diagram.

This diagram can be converted as following form called EBNF (Extended Backus-Naur Form).
  digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
  integer = [add operator], digit, {digit}
  real = [add operator], (digit, {digit}, ".", {digit} | {digit}, ".", digit, {digit})
  add operator = "+" | "-"
  multiply operator = "*" | "/"
  number = real | integer
  term = number, {multiply operator, number}
  expression = term, {add operator, term}
And this relationship will become program code of parsing.  For example, syntax of "number" is
  number = real | integer
The code of parsing "number" is as follows.

Sub Parse_GetNumber
  Parse_GetReal()
  If bMatched = "False" Then
    Parse_GetInteger()
  EndIf
EndSub

The whole program of calculator has been published as BQJ710-0.

What's a Parser Generator


Parser Generator is a program which generates parser program.  The input of parser generator is a syntax of language.

Sample Programs


There are two sample parser generator programs.  The first one generates Graphics Interpreter.  The second one generates Code Block Formatter.  These parser generators have subset of Small Basic language syntax for their input.

Parser Generator 0.4 for Graphics Interpreter


This program XWX066 generates Small Basic Graphics interpreter.  Save this program as "ParserGenerator04.smallbasic"  and remove comment mark from lines with File object. This program generates a interpreter named "SBGInterpreter04.smallbasic".
  • Subroutines start with Exec_, Lex_ and SBGI_ will be copied to the interpreter.
  • Subroutines start with PG_ are parser generator itself.
  • PG_Init is a core subroutine and contains syntax of Small Basic graphics as BNF format (but not strict BNF here).
  • Subroutine SB_GetSub gets subroutine source code from given file name.
Language syntax is defined as BNF. So, many languages can be parsed by changing BNF, such as Small Basic (of course), old type of BASIC, any markup languages or BNF itself etc.

* BNF : Backus-Naur Form
 

Parser Generator 1.4 for Code Block Formatter


This program ZBG977-4 generates Small Basic code block formatter.  Generated program has been uploaded as SKC235-2 and see the article "Small Basic: How to Format a Code Block" for it's detail.  Following code is a BNF syntax of Small Basic written in PG_Init subroutine in this parser generator.

  ' initialize syntax array
  syntax["state"] = "*[<token>]"                                        ' statement
  syntax["token"] = "{<kw>|<op>|<mem>|<real>|<_str>|<var>|<rem>|[]}"    ' token
  syntax["kw"] = "{For|To|Step|EndFor|If|Then|ElseIf|Else|EndIf|While|EndWhile|Goto|Sub|EndSub}"  ' 14 keywords
  syntax["op"] = "{+|-|'*'|/|=|'<'|'>'|'<='|'>='|'<>'|And|Or|(|,|)|:}"  ' operator
  syntax["mem"] = "<_name>[].[]<_name>"                                 ' member (property or event)
  syntax["var"] = "{<_name>|'['|']'}"                                   ' variable
  syntax["rem"] = "_SQ*"                                                ' remark (comment)
  syntax["real"] = "[-]<_num>[.<_num>]"                                 ' real number

See Also


Small Basic Parser Generator (an article in Small Basic Forum)
Leave a Comment
  • Please add 2 and 1 and type the answer here:
  • Post
Wiki - Revision Comment List(Revision Comment)
Sort by: Published Date | Most Recent | Most Useful
Comments
  • Nonki Takahashi edited Revision 20. Comment: fixed code blocks

  • Nonki Takahashi edited Revision 19. Comment: version up from Parser Generator 1.3 to 1.4

  • Nonki Takahashi edited Revision 18. Comment: wording

  • Nonki Takahashi edited Revision 17. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 16. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 15. Comment: changed sub title for TOC

  • Nonki Takahashi edited Revision 14. Comment: changed sub title for TOC

  • Nonki Takahashi edited Revision 13. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 12. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 11. Comment: anchor tag changed for TOC

Page 1 of 2 (13 items) 12
Wikis - Comment List
Sort by: Published Date | Most Recent | Most Useful
Posting comments is temporarily disabled until 10:00am PST on Saturday, December 14th. Thank you for your patience.
Comments
  • Nonki Takahashi edited Revision 7. Comment: Created

  • Nonki Takahashi edited Revision 8. Comment: tag changed for TOC

  • Nonki Takahashi edited Revision 9. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 10. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 11. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 12. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 13. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 14. Comment: changed sub title for TOC

  • Nonki Takahashi edited Revision 15. Comment: changed sub title for TOC

  • Nonki Takahashi edited Revision 16. Comment: anchor tag changed for TOC

  • Nonki Takahashi edited Revision 17. Comment: anchor tag changed for TOC

  • TOC for "Parser Generator 0.4 for Graphics Interpreter" can't be created.  Why?

  • Nonki Takahashi edited Revision 18. Comment: wording

  • Nonki Takahashi edited Revision 19. Comment: version up from Parser Generator 1.3 to 1.4

  • Nonki Takahashi edited Revision 20. Comment: fixed code blocks

Page 1 of 2 (19 items) 12