calc_infix2rpn, an Infix to Reverse Polish Notation (RPN) Compiler written in C++

Original document location.

Git Repository

This project's canonical repositories is hosted on Gothel Software.


This project demonstrates most elements of compiler design using C++

  • lexigraphical scanner via flex producing a token stream for
  • grammar parser via bison producing the intermediate representation (IR), here the actual RPN
  • semantic optimization of the IR (RPN in our case)
  • last but not least, allows to use the RPN - naturally

We test two lex-scanner generator in this little project, flex and RE/flex, together with the bison parser generator.

Supported Platforms

C++20 and better where bison and Re-flex or flex is supported.

Building Binaries

Build Dependencies

  • CMake 3.13+ but >= 3.18 is recommended
  • C++20 compiler
    • gcc >= 10
    • clang >= 15
  • Parser generator
  • Lexer generator
    • flex
      • using the C-interface with our prefix and reentrant
      • smallest code footprint experience
    • Re-flex >= 3.2.3 optional
      • using the C++ interface (only option)
      • hacked RTTI away, i.e. dynamic_cast -> static_cast.
      • code footprint a bit excessive due to its library
  • Optional for lint validation
    • clang-tidy >= 15
  • Optional for vscodium integration
    • clangd >= 15
    • clang-tools >= 15
    • clang-format >= 15

Installing build dependencies on Debian (11 or better):

apt install git
apt install build-essential g++ gcc libc-dev libpthread-stubs0-dev 
apt install clang-15 clang-tidy-15 clangd-15 clang-tools-15 clang-format-15
apt install cmake cmake-extras extra-cmake-modules pkg-config
apt install bison flex
apt install doxygen graphviz

Perhaps change the clang version-suffix of above clang install line to the appropriate version.

After complete clang installation, you might want to setup the latest version as your default.

Since Re-flex (optional) is not yet provided in a Debian distribution, it must be manually installed as described in its repository (easy) and will be picked up if found.

Build Procedure

The following is covered with a convenient build script.

For a generic build use:

git clone --recurse-submodule git://jausoft.com/srv/scm/cs_class/calc_infix2rpn.git
cd calc_infix2rpn
mkdir build
cd build
cmake ..
make -j $CPU_COUNT install doc

Our cmake configure has a number of options, cmake-gui or ccmake can show you all the options. The interesting ones are detailed below:

Changing install path from /usr/local to /usr


Building debug build:


Building with clang and clang-tidy lint validation


To build documentation run:

make doc

IDE Integration


IDE integration configuration files are provided for

  • Eclipse with extensions
    • CDT or CDT @ eclipse.org
    • CMake Support, install C/C++ CMake Build Support with ID org.eclipse.cdt.cmake.feature.group

You can import the project to your workspace via File . Import... and Existing Projects into Workspace menu item.

For Eclipse one might need to adjust some setting in the .project and .cproject (CDT) via Eclipse settings UI, but it should just work out of the box.

VSCodium or VS Code

IDE integration configuration files are provided for

For VSCodium one might copy the example root-workspace file to the parent folder of this project (note the filename change) and adjust the path to your filesystem.

cp .vscode/calc_infix2rpn.code-workspace_example ../calc_infix2rpn.code-workspace
vi ../calc_infix2rpn.code-workspace

Then you can open it via File . Open Workspace from File... menu item.

  • All listed extensions are referenced in this workspace file to be installed via the IDE
  • The local settings.json has clang-tidy enabled
    • If using clang-tidy is too slow, just remove it from the settings file.
    • clangd will still contain a good portion of clang-tidy checks