8.5 KiB
Parsodus
A language agnostic parser generator
Table Of Contents
Introduction
Parsodus is a language agnostic parser generator. Which means that it uses a description of a grammar in a kind of BNF notation, and outputs source files for a parser (which can be in any language for which a backend has been built, currently only c++), using a specified parsing algorithm (currently 4 kinds of LR parser have been implemented). This parser can then be augmented with rule handling to build an abstract structure representing the data, doing computations immediately, or anything else you can imagine. It's principle is very similar to the well known tools such as yacc or bison, which the difference that Parsodus has a simpler input format, and does not depend on language specific actions to be specified in the configuration file. It uses a programming language independent description of the grammar, along with optional naming for the rules, in order to allow a bigger reusability across different programming languages of the same parser specification.
This project came into existence as an application exercise in a course on languages and turing machines for the University of Antwerp, and can be considered a continuation of Lexesis (a lexical analyser generator).
Requirements
- git
- CMake 3.2.2+
- Boost variant header library (needed for mstch)
- Doxygen (optional, needed for building documentation)
For those still on Ubuntu Trusty, the default cmake version is still 2.8.12, so there is a ppa available with a more up-to-date version.
Run
sudo apt-get update && sudo apt-get -y install software-properties-common; \
sudo add-apt-repository -y ppa:george-edison55/cmake-3.x; \
sudo apt-get update && sudo apt-get install -y cmake
to get this newer version
Boost variant can be installed on an ubuntu machine by running
sudo apt-get update && sudo apt-get -y install libboost-dev
Used dependencies
The following dependencies will be automatically downloaded with git while building
Building
Get your terminal in the source tree and run the following commands:
mkdir build
cd build
cmake ..
make
sudo make install
You can now simply run Parsodus with the arguments you like (see below and in the man pages for an overview).
If you want to build the documentation as well, simply run
make doc
The output should be located in build/doc, with the main html page in build/doc/html/index.html.
Running tests
First, build Parsodus in debug mode. The first difference with the normal building, is the line where you call cmake. That line should read
cmake .. -DCMAKE_BUILD_TYPE=Debug -DCMAKE_INSTALL_PREFIX=.
instead. Afterwards, after calling make install (which now installs locally in the build folder, so you don't need the sudo), build all the examples as well with
cmake .
make examples
since they are used to test the functionality of the generated parsers.
To run the unit tests: simply run make test
To run the tests for the generated parser: build the examples and run python3 ./run_tests.py in the project root
Building examples
To build the examples: after running make install, run cmake . && make examples
You will now find the examples built in the example subdirectory of the build folder
Getting started
Now that Parsodus is successfully built and your terminal is in the build folder, it's time to generate the parser based on your input file.
The input file
Input files for Parsodus have a .pds extension and have a set of some very simple rules:
Variables in the grammar follow the regular expression <[a-zA-Z_][a-zA-Z0-9_]*>, and terminals use the same scheme, except using double quotes instead of angular brackets.
Furthermore, Parsodus uses a couple of key-value associations, including
- parser: the parsing algorithm to use
- terminals: a whitespace separated list of terminals
- lexesis (optional): a reference to a lexesis specification file. If given, terminals will be read from the lexesis file, and should as such not be specified separately in this file.
- precedence (optional): a whitespace separated list of
left,right, ornonassocfollowed by terminals, higher up is a higher precedence - start: a variable to use as the start symbol
- grammar: a list of rules (see below)
A grammar rule is a variable followed by ::= followed by a |-separated list of rule tails ended with a semicolon. A rule tail is a list of variables and terminals followed by an optional rule name of the form [name]. These annotations can additionally contain a specific precedence for this rule (a common example for this is the unary minus in mathematical expressions) in the form of a precedence specifier (left, right or nonassoc) followed by a non-negative integer. This integer specifies the precedence level for that rule (higher means higher precedence). Otherwise, the precedence for a rule is determined by the precedence of its last terminal. The lowest precedence in the precedence section of the file has precedence level 0.
parser: lalr(1)
terminals:
"A"
start: <s>
grammar:
<s> ::= "A" [single]
| "A" "A" [double]
;
We are building an LALR(1) parser, with replacement rules, both starting from the start-symbol <s>, named appropriately single and double.
Conventionally, terminals are all caps, while variables are lowercase.
Comments are from a # to the end of the line.
Using the parser
Of course, how you use the generated parser highly depends on which backend you used to generate it. For the default c++ backend however, the easiest way of getting to know the parser is probably having a look at the class definition in the generated header file, usually named <Parsername>.h. In general, there should be some way to run the parser, along with user defined actions, and get back the generated structure or abstract syntax tree.
Debugging the parser
Nobody is perfect, so it is unlikely a grammar will always be completely conflict free from the very first time. It will happen on several occasions that Parsodus will notify you of a problem with your and you're unable to simply see where things go wrong. Or maybe the parser is behaving differently than you would expect. That's why there is a command line option to Parsodus that allows you to inspect the decisions made by the generator.
For the LR based parsers, that means that the information about the action and goto table is written, along with information about the configuration sets leading to the actual parser states. Conflicting actions are indicated with a leading exclamation mark, to be able to easily find the exact source of your troubles.
Parsodus --debug emits a debug.log file to the same output directory as the generated parser.
Error recovery
If you provide a rule with <error> somewhere inside the body, this can be used to recover from errors. The generated parser will discard states until it encounters somewhere it can use such a rule. Afterwards, it will start discarding tokens until it can proceed in parsing. If it's impossible to recover from the error (cannot find a recovery rule or cannot find a synchronizing token before EOF), there will generally be an error (depending on the backend). Usually, some sort of reporting mechanism should also be in place by the generated parser.
<error> should never appear as the head of a grammar rule.
Bash completion
A file that provides bash completion is also provided for your convenience, to use it, do:
for a single session: source Parsodus-completion.bash
If you want it always, copy the file to /etc/bash_completion.d or your distro's equivalent location, and start a new shell.
More examples
More examples can be found in the examples subdirectory, go ahead an have a look at them. Feel free to play around and experiment with them.
Authors
- Thomas Avé
- Robin Jadoul
- Kobe Wullaert
License
This program is distributed under the terms of the MIT license. The generated code falls under the permissive zlib/libpng license.