FSharpCompiler.Parsing 1.1.3

The FSharpCompiler.Parsing is a runtime for parser.

The Yacc parser reads a sequence of tokens as its input, and groups the tokens using the grammar rules. If the input is valid, the end result is that the entire token sequence reduces to a single grouping whose symbol is the grammar’s start symbol.

Parse Tree

The ParseTree type describes a generic abstract syntax tree.

type ParseTree<'tok> =
    | Interior of symbol:string * children: list<ParseTree<'tok>>
    | Terminal of 'tok

An Interor node represents a production. The symbol is the result of the production, or the left side of the production. The children is the components of the production, or the right side of the production. An Terminal node represents a terminal symbol. The parameters of the node represent a token of the input stream.

The parse tree is implicitly constructed during the parse. As the parser executes, it builds an internal representation of the the structure of the program. The internal representation is based on the right hand side of the production rules. When a right hand side is recognized, it is reduced to the corresponding left hand side. Parsing is complete when the entire program has been reduced to the start symbol of the grammar.

Syntactic Parser

The type SyntacticParser is a model of a parsing table driven parser.

To construct SyntacticParser type, you need to provide parsing table that be written by hand or be automatically generated By Yacc.

open FSharpCompiler.Parsing
let private parser = 
    SyntacticParser(
        ExprParsingTable.rules,
        ExprParsingTable.kernelSymbols,
        ExprParsingTable.parsingTable)

Provides a function that associates terminal symbol in grammar input file with the token in source stream. and let's assemble a parsing function:

let parseToTree tokens = 
    parser.parse(tokens, Tokenizer.getTag) 

We can now test it on some sample inputs:

let x = [Number 1.0;Plus;Number 2.0]
let y = parsingTree x
Should.equal y 
<| Interior("expr",[Interior("expr",[Terminal(Number 1.0)]);Terminal Plus;Interior("expr",[Terminal(Number 2.0)])])

How to build a parser using FSharpCompiler.Parsing is detailed in the resolution: xp44mm/ArithmeticExpressions