Datei:Parsing a C program that needs 2 token lookahead.pdf
Es ist keine höhere Auflösung vorhanden.
Parsing_a_C_program_that_needs_2_token_lookahead.pdf (647 × 560 Pixel, Dateigröße: 33 KB, MIME-Typ: application/pdf)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
| Beschreibung |
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 Aufl.), 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). |
| Datum | |
| Quelle | Eigenes Werk |
| Urheber | Jochen Burghardt |
| Andere Versionen | 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}
|
Lizenz
Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:
Diese Datei ist lizenziert unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 international“.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
| Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
|---|---|---|---|---|---|
| aktuell | 17:17, 8. Feb. 2019 |  | 647 × 560 (33 KB) | Jochen Burghardt | User created page with UploadWizard |
Dateiverwendung
Keine Seiten verwenden diese Datei.