File:Parsing a C program that needs 2 token lookahead.pdf
No higher resolution available.
Parsing_a_C_program_that_needs_2_token_lookahead.pdf (647 × 560 pixels, file size: 33 KB, MIME type: application/pdf)
Captions
Captions
Add a one-line explanation of what this file represents
Summary
edit| Description |
English: Shows a C program that cannot be parsed with less than 2 token lookahead. The table at the top shows a simplified excerpt of the C grammar, taken from Brian W. Kernighan and Dennis M. Ritchie (Apr 1988) The C Programming Language, Prentice Hall Software Series (2nd ed.), Englewood Cliffs/NJ: Prentice Hall ISBN: 0131103628. (Appendix A.13 "Grammar", p.193 ff). The bottom part shows a parser that has digested the tokens "
int v ;main(){" (grey background) and is about choose a rule to derive the nonterminal "Stmt". Looking only at the first lookahead token "v" (red background), it cannot decide which of both alternatives for "Stmt" to choose. Two possible continuations are shown (white background) that would require different alternatives to choose. However, by peeking at the second lookahead symbol (yellow background), an appropriate decision can be taken.Français : La grammaire C n’est pas LL (1): la partie inférieure montre un analyseur qui a digéré les jetons " int v ;main(){" et qui concerne le choix d’une règle pour dériver le non-terminal "Stmt". En regardant uniquement le premier jeton d'anticipation "v", il ne peut pas choisir laquelle des deux alternatives pour "Stmt" choisir, étant donné que deux suites d'entrées sont possibles. Ils peuvent être distingués en jetant un coup d'œil sur le deuxième jeton d'anticipation (fond jaune). |
| Date | |
| Source | Own work |
| Author | Jochen Burghardt |
| Other versions | File:Parsing a C program that needs 2 token lookahead.svg |
| LaTeX source code |
|---|
\usepackage[pdftex]{color}
\usepackage{amssymb}
\usepackage[paperwidth=110\unitlength,paperheight=95\unitlength]{geometry}
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{110\unitlength}
\setlength{\textheight}{95\unitlength}
\setlength{\oddsidemargin}{-23mm}
\setlength{\parindent}{0cm}
\renewcommand{\arraystretch}{1.3}
\pagestyle{empty}
% foregound colors
\definecolor{fBnf} {rgb}{0.00,0.60,0.00} % BNF meta symbol
\definecolor{fTrm} {rgb}{0.00,0.00,0.80} % terminal symbol
\definecolor{fLin} {rgb}{0.30,0.30,0.30} % nonterm extension line
\definecolor{fThis} {rgb}{0.90,0.00,0.00} % currrent nonterminal
% backgound colors
\definecolor{bPast} {rgb}{0.75,0.75,0.75} % already consumed
\definecolor{bThis} {rgb}{0.99,0.75,0.75} % next symbol
\definecolor{bNext} {rgb}{0.99,0.99,0.50} % current symbol
\newcommand{\trm}[1]{\textcolor{fTrm}{\large\texttt{#1}}}
\newcommand{\bnf}[1]{\textcolor{fBnf}{\large\textsf{#1}}}
\newcommand{\opt}[1]{\bnf{[} #1 \bnf{]}}
\newcommand{\seq}[1]{#1\bnf{$^*$}}
\newcommand{\alt}{\bnf{ ! }}
\newcommand{\dfn}{\bnf{::=}}
\begin{document}
% Appendix A.13 "Grammar" (p.193 ff)
%
% Trns translation-unit
% ExtDecl external-declaration
% FunDef function-definition
% Decl declaration
% DeclSpec declaration-specifiers
% Dc declarator
% CompStmt compound-statement
% Stmt statement
% AssgExpr assignment-expression
% Id identifier
\begin{tabular}{|l@{$\;$}l@{$\;$}l|}
\hline
Trns & \dfn & ExtDecl
\alt Trns ExtDecl \\
ExtDecl & \dfn & FunDef
\alt Decl \\
FunDef & \dfn & \opt{ DeclSpec } Dc \opt{ \seq{Decl} } CompStmt \\
CompStmt & \dfn & \trm{\{} \opt{ \seq{Decl} } \opt{ \seq{Stmt} } \trm{\}} \\
Stmt & \dfn & Id \trm{:} Stmt
\alt \opt{AssgExpr} \trm{;}
\alt \ldots \\
AssgExpr & \dfn & Id \trm{=} AssgExpr
\alt \ldots \\
\hline
\end{tabular}
\newcounter{curX}
\newcounter{curY}
\newcommand{\startText}[2]{%
\setcounter{curX}{#1}%
\setcounter{curY}{#2}%
}
\newcommand{\addText}[2]{%
\put(\arabic{curX},\arabic{curY}){\makebox(0,0)[b]{\trm{#1}}}%
\addtocounter{curX}{#2}%
}
\renewcommand{\_}[1]{\addText{#1}{4}}
\renewcommand{\.}[1]{\addText{#1}{2}}
\newcommand{\rect}[2]{\rule{#1\unitlength}{#2\unitlength}}
\newcommand{\lin}[1]{\textcolor{fLin}{\rect{#1}{0.1}}}
\begin{picture}(75,50)(-15,0)
\textcolor{bPast}{\put(2,6){\makebox(0,0)[bl]{\rect{38}{7}}}}%
\textcolor{bThis}{\put(40,6){\makebox(0,0)[bl]{\rect{4}{7}}}}%
%
\startText{4}{7}%
\.i\.n\.t\.{ }%
\_v%
\_;%
\.m\.a\.i\.n\.{ }%
\_(%
\_)%
\_\{%
\_v%
%
\textcolor{bNext}{\put(44,0){\makebox(0,0)[bl]{\rect{4}{19}}}}%
%
\startText{46}{1}%
\_:%
\.r\.e\.t\.u\.r\.n\.{ }%
\_0%
\_;%
\_\}%
%
\startText{46}{13}%
\_=%
\_0%
\_{ }%
\_{ }%
\_{ }%
\.{ }%
\_;%
\_\}%
%
\textcolor{fThis}{\put(40,20){\makebox(0,0)[bl]{Stmt\lin{21}}}}%
%
\put(2,25){\makebox(0,0)[bl]{Decl\lin{7}}}%
\put(19,25){\makebox(0,0)[bl]{Dc\lin{11}}}%
\put(40,25){\makebox(0,0)[bl]{CompStmt\lin{10.5}}}%
%
\put(2,30){\makebox(0,0)[bl]{ExtDecl}}%
\put(19,30){\makebox(0,0)[bl]{FunDef\lin{41}}}%
%
\put(19,35){\makebox(0,0)[bl]{ExtDecl\lin{39.5}}}%
\put(2,35){\makebox(0,0)[bl]{Trns\lin{7}}}%
%
\put(2,40){\makebox(0,0)[bl]{Trns\lin{63}}}%
\end{picture}
\end{document}
|
Licensing
editI, the copyright holder of this work, hereby publish it under the following license:
This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.
- You are free:
- to share – to copy, distribute and transmit the work
- to remix – to adapt the work
- Under the following conditions:
- attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 15:17, 8 February 2019 |  | 647 × 560 (33 KB) | Jochen Burghardt (talk | contribs) | User created page with UploadWizard |
You cannot overwrite this file.
File usage on Commons
There are no pages that use this file.