Home

Links

• Concepts - a short overview of compilers and how Froley fits in.
• Token Type Definitions - how to define token types.
• Scanner Command Reference - Scanner coding reference .
• Parser Command Reference - Parser coding reference.

.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 Definitions), [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-Interpreter example.

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

main

--------------------------------------------------------------------------------
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 standard match (also called match input) uses an efficient scan table technique to read the longest match among its constituent produceAny and individual case comparisons. In this case any symbols of the Symbols token group is matched then a corresponding Token is produced. produceing 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 produces a Token if it can, so if the routine returns (instead of the Scanner restarting) then it was unable to scan a token.
• The final command is syntaxError, which generates an "Unexpected input" error.

scan_id_or_keyword

- 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 (not shown here) can be used to transmit information across routine calls.
• 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

- 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 underscore (_) characters from the input. Numbers such as 123_456 are tokenized as 123456.

scan_integer, scan_string

- 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.
• New extended Cmd node types are created automatically when used in a create or produce command. create Println(args) says: "Extend a new node type called Println with a single property args:Cmd. Instantiating a Println pops one node off the internal stack and stores it as args. The new Println node is then pushed on the stack."

consume_eols, arg_list

- consume_eols
  while (consume(EOL)) noAction

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

expression, assign

- expression
  assign

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

• A [rightBinary] routine facilitates the construction of right-associative operator subtrees. If the input tokens were [a = b = c], the resulting subtree here would be Assign( Access(a), Assign(Access(b),Access(c)) ), reflecting the order of operations (a = (b = c)).
• Any "operation shorthand" routine (rightBinary, binary, preUnary, postUnary) implicitly pulls its higher-precedence operands from the next routine below it, so assign [rightBinary] gets its operands by calling add_subtract.
• Cmd node type Assign will automatically be defined and will extend built-in base type Binary.
• -> is shorthand for produce.
• Only on-produce (e.g. on ... -> NodeType) statements can be used in operator shorthand routines.
• An operator shorthand routine automatically returns a single node from the next routine down if no on matches are found.

Binary Operators

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

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

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

• A [binary] routine is a left-associative binary operator shorthand routine. Input tokens [a + b + c] would result in the subtree Add( Add(Access(a),Access(b)), Access(c) ), reflecting the order of operations ((a + b) + c). Node types Add, Subtract, Multiply, Divide, and Power would automatically be defined as extended Binary nodes.

Unary Operators

- factorial [postUnary]
  on "!" -> Factorial

- negate [preUnary]
  on "-" -> Negate

• The two routines above would parse input tokens [- 5 !] into the subtree Factorial( Negate(Number(5)) ).

term

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

• Parens (()) control the order of parsing but do not need to create any additional structure.
• Here we see on '(' with two additional parts: expression and ). Only the first part of a multi-part on is checked as part of the condition and the remainder become expected parts. For example:

Equivalent statements for on '(' expression ')': return

#{
on '('
  expression
  mustConsume ')'
  return
endOn
}#

• Node properties (like args in Println(args)) normally have the default type Cmd.
• Properties may also be declared as any extended node type (Println(args:Args)) or as one of the five built-in types String, Real, Integer, Character, and Logical.
• If a node type property is assigned the value content then the string .content of the current token (set by the enclosing on) is passed as the argument. A property assigned content defaults to type String but can be explicitly declared as one of the four other built-in primitive types.

Additional Nodes

# 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)

• As seen previously, a command such as Access(name=content) creates an Access class with a name:String property, with the string value's taken from the current token's content.
• Consider here the additional functionality of declaring ReadVar(name:String) without the =content value assignment. In this case a node is popped off the internal stack and to->String is called on it. Therefore WriteVar(name:String,new_value) pops two Cmd nodes off the stack. new_value is assigned a reference the most recent node and name is assigned the older node .to->String.