Lexer/Parser for multidimensional Languages

Question

How does Lexer/Parser work in a 2D programming language like Funciton in order to transform such an unusual source-code to the correct AST?

Answer 1

Layout sensitive languages are an unusual occurrence because they are a bit more difficult to parse. A token produced by a lexer will not only contain a type and a value, but also a position and maybe a size. It is possible that the lexer will not proceed linearly line by line, but will first read the whole file into memory and then traverse it as a 2D map.

Layout-sensitive parsing or indentation-sensitive parsing is a small but still active field of research; investigating these terms will provide you with a number of papers. In easy cases like Python, we can use a stateful lexer that hides the indentation from a parser, and instead emits phantom tokens like INDENT and DEDENT which would be the equivalent to curly braces in C. In more complex cases, we need to annotate the parser's grammar with requirements on the indentation, e.g. the enhanced context free grammar

DoExpression{n} ::= "do"{n} DoExpressionInner{m: m > n}
DoExpressionInner{n} ::= Expression{n}+

might allow

do expr1
   expr2
   expr3

but not

do expr1
     expr2
expr3

In the above grammar, the expression in curly braces puts a condition on the position of the left edge of the rule or token. Most parser generators do not support such layout parsing.

In the most general case, a lexer would have to recognize shapes in the textual input. A parser would then likely use bottom-up techniques to group the primitive shapes into a usable data structure, likely a non-hierarchical graph. For example, the image

  012345678901234567890123456789
0 +---+
1 | A |-----------.
2 +---+           |        +---+
3                 '------->| B |
4                          +---+

could be lexed as:

BOX "A" at ( 0, 0) to ( 4, 2)
BOX "B" at (25, 2) to (29, 4)
ARROW   at ( 5, 1) to (24, 3)

These tokens could then be stored in a manner supporting spatial lookup. Starting with the A box, we can look at the surrounding fields and will find the start of the arrow. At the end of the arrow, we find the B box and can therefore add this connection between A and B to the Abstract Syntax Graph. After that, the arrow can be removed from the set of unused tokens. As no other tokens are in the A box's immediate neighborhood, it too can be removed, ditto for B. As the set of uninspected tokens is empty, the parse has succeeded.

Parsing Funciton is easier than parsing such ASCII art, as the used symbols directly show connections. It might therefore be possible to parse the source in a single pass: once any element is found, we can follow the connections and add the appropriate connections to our Abstract Syntax Graph.

Most languages that use graphs to represent data or a program do not use a 2D textual representations. Instead, they will provide IDEs that represent render the structure as a graph, but store it as a more easily processed form. Likely, the connections would be stored by IDs rather than by spatial locations, although the layout would be part of the stored information. LabView is probably one of the best-known visual programming languages that use graphs to represent control/data flow, but do not offer a textual representation of the program.

Answer 2

It is just dataflow: only the visual representation displayed to the user is 2D. Internally, this is a graph structure with a list of nodes and a list of vertices.

Look at VHDL, Verilog or any hardware description language for text-based dataflow languages.

Look at Excel or any spreadsheet for another representation of dataflow language.

The main difference is not in parsing, it is in runtime.

EDIT

The Funciton language actually is very specific in that source code is sort of ASCII art of boxes and edges. The first commit of the interpreter gives the general algorithm used for parsing that ASCII art:

1. Find boxes and their outgoing edges
   • Start finding a box here if this is a top-left corner of a box
   • Find width of box by walking along top edge
   • Find height of box by walking along left edge
   • Verify the bottom edge
   • Verify the right edge
   • ...
2. Parse the connections between nodes and discover all the loose ends ...