Summary:

This project is about creating a simple shell.

To build project with run cmake:

mkdir -pv build; cd build
cmake ..
cmake --build . --target all

To run valgrind with readline suppressions:

valgrind --leak-check=full \
  --show-leak-kinds=all \
  --suppressions=supp.supp ./minishell

• if you find the output is mixed with the application output then redirect valigrind output to separate file descriptor:

  valgrind --leak-check=full \
        --show-leak-kinds=all \
        --suppressions=supp.supp \
        --log-fd=9 ./minishell \
        9>>memcheck.log

Lexer-parser

Traditionally, syntax analysis is divided into a lexical scanner and a (context-free) parser. A scanner divides an input string consisting of characters into a string of tokens. A sequence of input characters t h a t comprises a single token is called a lexeme. Thus, lexical analyzer insulates a parser from the lexeme representation of tokens.

Tokenizing is breaking up a string in chunks. The lexical properties of the chunks are defined by the lexer rules. Such a chunk is like a word in a sentence. This tokenization is usually based on regular expression matching. To choose between overlapping matches a number of standard lexical disambiguation rules are used. (Advanced feature: A lexer can be put in a certain state, after seeing a certain input. These states can determine which rules are enabled/disabled.) Each lexer rule gets an identifier called a token, typically an integer. So the output of the lexer is a stream of tokens (integers) that represent the regular expressions it has seen in the input string. This output also allows seeing what part of the input string was recognized for each token. Lexer rules can overlap. Simple precedence logic applies to decide which rules will be matched. Internally a lexer (like lex or flex) has a generated state-machine that keeps track of all this.

• Token Recognition
• vsinha CS-252 Fall 2013
• offirgolan lexical analyzer for shell

A next step is feeding these tokens to a parser which has grammatical rules that define what order of tokens form valid input.

• Shell Grammar
• Scannerless Generalized LR Parsers

Bison:

bison --report=state shell.y

• Parsing - wiki
• Pratt Parsing
• Top-Down operator precedence
• Precedence Climbing
• Recursive Descent
• A recursive descent with infix expression
• Let’s Build a Linux Shell
• Scannerless parsing
• BNF for parsing AND lexing

Shell variable expansion:

• 3.5 Shell Expansions - gnu.org

Syntax trees:

A concrete syntax tree matches what the grammar rules say is the syntax. The purpose of the abstract syntax tree is have a "simple" representation of what's essential in "the syntax tree".

• AST vs BST

Executing:

• Shell Implementation of Pipelines

Useful links:

• LALR(1) grammars
• DMSToolkit

Other implementations:

• Thomas Wagner's minishell
• Toni Schmitt's minishell
• Open Edu Hub - OSdev - minishell
• Vincent Sanders's GNU dbm