Loading page…
Master the fundamental concepts of syntax analysis through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksYacc and GNU Bison compile a context-free grammar plus semantic actions into an LALR or GLR parser table and C code. PostgreSQL's SQL parser, Bash, and countless domain languages are built with Bison. Understanding generated output demystifies shift/reduce conflicts.
Write a .y file: %token declarations, grammar rules with actions, %% separator, and user code. Bison emits yyparse(), token enums, and the ACTION/GOTO tables. Semantic actions build the AST as reductions fire.
yaccLoading…
%left and %right declare precedence and associativity$$ is the LHS value; $1, $2 are RHS slotsyylex() for tokensProduction compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.
You will use Yacc/Bison to generate a parser and study the emitted tables and C code. This exercise requires writing a grammar with semantic actions, resolving conflicts, and tracing how Bison's output drives parsing.
Bison can't run in this sandbox, so you'll implement what Bison generates for the classic infix calculator from the Bison manual, including the part that makes Bison interesting: how %left, %right and %precedence resolve the shift/reduce conflicts of an ambiguous grammar.
yaccLoading…
The grammar alone is ambiguous (1 - 2 - 3 has two parse trees). Bison resolves each conflict between a rule and a lookahead token by precedence: declarations further down bind tighter; on a tie, %left reduces and %right shifts. So * beats +, 1 - 2 - 3 is (1 - 2) - 3, 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2), and because NEG is below ^, -2 ^ 2 is -(2 ^ 2).
One expression per line; blank lines are ignored. Tokens: NUM (a run of digits), + - * / ^ ( ). Spaces and tabs are ignored.
For each line:
cLoading…
REDUCTIONS lists, in the order the LALR parser performs them, one item per reduction: the number for exp: NUM, the operator for a binary rule, neg for unary minus. The '(' exp ')' rule prints nothing. (This is the tree in postfix order.)VALUE is computed with 64-bit signed integers: / truncates toward zero, ^ is repeated multiplication with a non-negative exponent (x ^ 0 is 1).division by zero instead of the value; for a negative exponent print negative exponent.INPUT => syntax error (Bison's default message).INPUT is the line exactly as read.
Input:
cLoading…
Output:
cLoading…
$$ = $1 + $3 and so on).Hidden tests mix unary minus with every operator, deep parentheses, division truncation, and include division by zero, a negative exponent and several syntax errors.