Skip to content

Home

Jump to bottom
Abe Pralle edited this page Nov 23, 2021 · 20 revisions

Links

.froley Files

A .froley file is used to define token types and write the logic for the Scanner and Parser. Name it with the name of the language you're defining - for example, Simple.froley for a language called "Simple".

Sections

A .froley file is comprised of three sections: [tokens](Token Type Definition Reference), [scanner](Scanner Command Reference), and [parser](Parser Command Reference).

Comments

There are four types of comments in Froley:

# Single-line comment
#{ Multi-line comment }#
==== Single-line "HR" comment
---- Single-line "HR" comment

Annotated Example

Taken from the "Simple" examples in the Examples/ folder.

Token Definitions

--------------------------------------------------------------------------------
tokens
--------------------------------------------------------------------------------

tokens begins an unnamed group of token type definitions. Note that ---- begins a single-line comment so the "HR" bars are for visual formatting only.

EOL(end of line)
IDENTIFIER identifier [content]
NUMBER     number     [content]
STRING     string     [content]

Sets of token type names, symbols, and optional [attributes]. Symbols can't have any spaces as part of them unless you declare the token types using the NAME(symbol) variation. [content] is a built-in attribute type that causes created tokens to automatically have a copy of the Scanner's scan buffer as the token's content string.

--------------------------------------------------------------------------------
tokens Symbols
--------------------------------------------------------------------------------
SYMBOL_BANG        !
SYMBOL_CARET       ^
SYMBOL_CLOSE_PAREN )  [structural]
SYMBOL_EQUALS      =
SYMBOL_MINUS       -
SYMBOL_OPEN_PAREN  (
SYMBOL_PLUS        +
SYMBOL_SLASH       /
SYMBOL_STAR        *

A named token-type group for symbols. The group name can be used to match scan buffer content with token symbols en masse.

--------------------------------------------------------------------------------
tokens Keywords
--------------------------------------------------------------------------------
KEYWORD_PRINTLN println

A named group for keywords. Keywords should be kept separate from symbols because of different scanning mechanisms used. For example, if the Scanner scans ++ it does not need to read further characters to classify ++ as an increment operator. On the other hand if else is scanned, it cannot be classified as the else operator because the next characters might be where for a variable named elsewhere. Keyword matching must first read a complete ID and then check for keywords.

Scanner

--------------------------------------------------------------------------------
scanner
--------------------------------------------------------------------------------
- main
  consume [ \r\t]*  # whitespace
  if (consume('\n')) produce EOL

  # single-line comment
  if consume("#" [^\n]*) restart

  if (not hasAnother) halt
  markPosition

  match
    produceAny Symbols
  endMatch

  scan_id_or_keyword
  scan_number
  scan_string

  syntaxError

  • main is the topmost routine so it becomes the start routine.

  • The start routine will be repeatedly called until a halt command is executed. The general approach is to produce one new Token each "pass".

  • consume can operate on characters, strings, or patterns. If the specified sequence can be read from the input, that sequence is discarded and consume returns true. Otherwise nothing is read (no partial matches) and consume returns false.

  • Patterns are a simple form of RegEx comprised of the following pattern elements:

    • Curly braces {...} can be used to unambiguously enclose an entire pattern sequence.
    • Single and double-quote strings are literals that must be matched exactly.
    • [...] defines a set of single characters, any single one of which can be read to match that pattern element.
    • [^...] matches any single character except those listed - "NOT these".
    • [A-Z] matches any single character between A and Z. Mix and match: [A-Za-z_] etc.
    • Following a pattern element with *, +, or ? allows it to occur zero or more times, one or more times, or optionally (at most once), respectively.

  • restart abandons the current pass and restarts at the start routine.

  • hasAnother returns true as long as there are any characters waiting to be read from the input.

  • markPosition uses the current line and column of input the next time a Token is created.

  • A regular match (also called match input) uses an efficient scan table technique to read the longest match among its constituent mass-produceAny and individual case comparisons. In this case of any of the Symbols token group is matched then a corresponding Token is produced. Producing a Token automatically adds it to the output queue and restarts the Scanner at the start routine.

  • scan_id_or_keyword, scan_number, and scan_string are all routine calls. Each routine is defined to either produce a Token or return if unsuccessful.

  • The final command is syntaxError, which generates an "Unexpected input" error.

    • scan_id_or_keyword if (not scan([_a-zA-Z][_a-zA-Z0-9]*)) return match buffer produceAny Keywords others: produce IDENTIFIER endMatch

  • Routines cannot accept any parameters or return any values. However global variables can be used to transmit information across routine calls (not shown here).

  • scan is like consume except instead of discarding the matching input, the characters are stored in the internal scan buffer. So if scan(...) returns true then a matching set of characters is stored in buffer.

  • match buffer attempts to match the characters in the scan buffer against the listed symbols and cases. The entire buffer must be matched to count as a match. If there are no matches then the others block is executed if defined.

  • Per standard approach, keywords should be handled by first reading a complete identifier and then attempting to match it with a defined keyword.

  • The IDENTIFIER token type is defined with the attribute [content], so a new IDENTIFIER token will automatically get a copy of the scan buffer as its .content string.

    • scan_number if (not hasAnother) return

      if (scan [0-9]) scan_integer if (scan '.') scan_integer produce NUMBER elseIf (scan '.') scan_integer produce NUMBER else return endIf

scan_number could be simpler if we weren't filtering out _ characters from the input. Numbers like 123_456 are equivalent to 123456.

- scan_integer
  while hasAnother
    if (not scan([0-9]) and not consume('_'*)) return
  endWhile
  return

- scan_string
  if (not consume('"')) return
  while (hasAnother and not nextIs('\n'))
    ch = read
    if (ch == '"') produce STRING
    elseIf (ch == '\\' and hasAnother) ch = read
    collect ch
  endWhile
  syntaxError "Unterminated string."

Parser

Whereas the Scanner produces tokens onto a queue, with each token being independent of every other token, the Parser produces Cmd nodes onto a stack. Each command node produced removes zero or more nodes from the stack as its properties and then is itself added to the stack. The stack should have a single node on it - the root of the AST - when the start routine returns.

parser

  • statements consume_eols

    beginList while (hasAnother) on "println" arg_list create Println(args) elseOthers expression endOn consume_eols endWhile produceList Statements

  • consume_eols is a call to another routine (not built-in).

  • beginList marks the current top of the node stack. When produceList is later called, all nodes since become part of an extended CmdList arbitrarily called Statements.

  • hasAnother returns true as long as there is another unread Token available. The input tokens are automatically set up to come from the Scanner's output.

  • on "println" behaves like consume("println") with the additional behavior of making that consumed Token the current token stored with the next created or produced Cmd node.

  • Tokens can be consume'd or scan'd using either their "symbol" or their TOKEN_NAME.

  • In the Scanner, produce creates a Token and then restarts the Scanner. In the Parser, produce creates a new command node and returns from the current routine.

  • create is like produce except the current routine continues instead of being return'd from.

    • consume_eols while (consume(EOL)) noAction

    • arg_list beginList while (hasAnother and not nextIs(EOL)) expression endWhile produceList Args

    • expression assign

    • assign [rightBinary] on "=" -> Assign

  • A [rightBinary] routine facilitates the construction of right-associative operator subtrees. If the token content were a = b = c, the resulting subtree here would be Assign( Access(a), Assign(Access(b),Access(c)) ).

  • All "operation shorthand" routines (rightBinary, binary, preUnary, postUnary) implicitly pull their higher-precedence operands from the next routine. So

  • -> shorthand

    • add_subtract [binary] on "+" -> Add on "-" -> Subtract

    • multiply_divide [binary] on "*" -> Multiply on "/" -> Divide

    • power [binary] on "^" -> Power

    • factorial [postUnary] on "!" -> Factorial(operand)

    • negate [preUnary] on "-" -> Negate(operand)

    • term on '(' expression ')': return on IDENTIFIER -> Access(name=content) on NUMBER -> Number(value=content:Real) on STRING -> LiteralString(value=content) syntaxError

    This routine is not called but its commands cause additional necessary node defs to be generated

    • additional_nodes create ReadVar(name:String) create WriteVar(name:String,new_value:Cmd)

Clone this wiki locally