Перейти к содержанию

Файл:Parsing a C program that needs 2 token lookahead.pdf

Содержимое страницы недоступно на других языках.
Перейти на страницу файла на Викискладе
Материал из Википедии — свободной энциклопедии
Исходный файл (647 × 560 пкс, размер файла: 33 КБ, MIME-тип: application/pdf)

Краткое описание

Описание
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).
Дата
Источник Собственная работа
Автор Jochen Burghardt
Другие версии 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}

Лицензирование

Я, владелец авторских прав на это произведение, добровольно публикую его на условиях следующей лицензии:
w:ru:Creative Commons
атрибуция распространение на тех же условиях
Вы можете свободно:
  • делиться произведением – копировать, распространять и передавать данное произведение
  • создавать производные – переделывать данное произведение
При соблюдении следующих условий:
  • атрибуция – Вы должны указать авторство, предоставить ссылку на лицензию и указать, внёс ли автор какие-либо изменения. Это можно сделать любым разумным способом, но не создавая впечатление, что лицензиат поддерживает вас или использование вами данного произведения.
  • распространение на тех же условиях – Если вы изменяете, преобразуете или создаёте иное произведение на основе данного, то обязаны использовать лицензию исходного произведения или лицензию, совместимую с исходной.

Краткие подписи

Добавьте однострочное описание того, что собой представляет этот файл

Элементы, изображённые на этом файле

изображённый объект

560 пиксель

647 пиксель

application/pdf

История файла

Нажмите на дату/время, чтобы посмотреть файл, который был загружен в тот момент.

Дата/времяМиниатюраРазмерыУчастникПримечание
текущий15:17, 8 февраля 2019Миниатюра для версии от 15:17, 8 февраля 2019647 × 560 (33 КБ)Jochen BurghardtUser created page with UploadWizard

Нет страниц, использующих этот файл.

Метаданные