数学代考| Backus Naur Form 离散数学代写代写 - 代考代写：100%准时可靠您的作业代写专家

Backus Naur form $^{5}$ (BNF) provides an elegant means of specifying the syntax of programming languages. It was originally employed to define the grammar for the Algol-60 programming language [2], and a variant was used by Wirth to specify the syntax of the Pascal programming language. BNF is widely used and accepted today as the way to specify the syntax of programming languages.

BNF specifications essentially describe the external appearance of programs as seen by the programmer. The grammar of a context free grammar may then be input into a parser (e.g. Yacc), and the parser is used to determine if a program is syntactically correct or not.

A BNF specification consists of a set of production rules with each production rule describing the form of a class of language elements such expressions, statements and so on. A production rule is of the form:
$$
<\text { symbol }>\quad::=\quad \text { }
$$
${ }^{3} \mathrm{~A}$ linear bounded automaton is a restricted form of a nondeterministic Turing machine in which a limited finite portion of the tape (a function of the length of the input) may be accessed.
${ }^{4} \mathrm{~A}$ pushdown automaton is a finite automaton that can make use of a stack containing data, and it is discussed in Chap. $7 .$
${ }^{5}$ Backus Naur Form is named after John Backus and Peter Naur. It was created as part of the design of the Algol 60 programming language, and is used to define the syntax rules of the language.
196
12 Language Theory and Semantics
where is a nonterminal, and the expression consists of sequenc of terminal and nonterminal symbols. A construct that has alternate forms appears more than once, and this is expressed by sequences separated by the vertical bar “‘”” (which indicates a choice). In other word, there is more than one possible substitution for the symbol on the left-hand side of the rule. Symbols that never appear on the left-hand side of a production rule are called terminals.

The following example defines the syntax of various statements in a sample programming language:
$::=\langle$ while loop $\rangle \mid<$ for loop $>$
$<$ while loop $>::=$ while $(<$ condition $>)<$ statement $>$
$<$ for loop $>::=$ f or $(<$ expression $>)<$ statement $>$
:: = |
$<$ assignment statement $>::=\langle$ variable $\rangle:=\langle$ expression $\rangle$
This is a partial definition of the syntax of various statements in the language. It includes various nonterminals such as (,\langle$ while loop $\rangle$ and so on. The terminals include ‘while’, ‘for’, ‘ $:=$ ‘, ‘(‘” and ” “)’. The production rules for $<$ condition $>$ and are not included.

The grammar of a context free language (e.g. $\operatorname{LL}(1), \operatorname{LL}(k), \operatorname{LR}(1), \operatorname{LR}(k))$ grammar expressed in BNF notation) may be translated by a parser into a parse table. The parse table may then be employed to determine whether a particular program is valid with respect to its grammar.
Example 12.1 (Context Free Grammar)
The example considered is that of parenthesis matching in which there are two terminal symbols and one nonterminal symbol

图论代考

Backus Naur 形式 $^{5}$ (BNF) 提供了一种指定编程语言语法的优雅方法。它最初用于定义 Algol-60 编程语言 [2] 的语法，Wirth 使用了一个变体来指定 Pascal 编程语言的语法。 BNF 作为指定编程语言语法的方式，在今天被广泛使用和接受。

BNF 规范本质上描述了程序员所看到的程序的外观。然后可以将上下文无关文法的文法输入到解析器（例如 Yacc）中，并且解析器用于确定程序在语法上是否正确。

BNF 规范由一组产生式规则组成，每个产生式规则描述一类语言元素的形式，如表达式、语句等。生产规则的形式为：
$$
<\text { 符号 }>\quad::=\quad \text { <带符号的表达式 > }
$$
${ }^{3} \mathrm{~A}$ 线性有界自动机是非确定性图灵机的一种受限形式，其中可以访问磁带的有限有限部分（输入长度的函数）。
${ }^{4} \mathrm{~A}$ 下推自动机是一种有限自动机，可以利用包含数据的堆栈，在第 1 章中对其进行了讨论。 $7 .$
${ }^{5}$ Backus Naur 形式以 John Backus 和 Peter Naur 命名。它是作为 Algol 60 编程语言设计的一部分而创建的，用于定义该语言的语法规则。
196
12 语言理论和语义学
其中是一个非终结符，表达式由终结符和非终结符的序列组成。具有替代形式的结构出现不止一次，这由用竖线“’”“分隔的序列表示（表示选择）。换句话说，左边的符号有多个可能的替换- 规则的左手边。从不出现在产生式规则左手边的符号称为终结符。

以下示例定义了示例编程语言中各种语句的语法：
<循环语句> $::=\langle$ while 循环 $\rangle \mid<$ for 循环 $>$
$<$ while 循环 $>::=$ while $(<$ 条件 $>)<$ 语句 $>$
$<$ for 循环 $>::=$ f 或 $(<$ 表达式 $>)<$ 语句 $>$
<语句> :: = <赋值语句> | <循环语句>
$<$ 赋值语句 $>::=\langle$ 变量 $\rangle:=\langle$ 表达式 $\rangle$
这是该语言中各种语句的语法的部分定义。它包括各种非终结符，例如 (、\langle$ while loop $\rangle$ 等。终结符包括’while’、’for’、’$:=$’、'(‘”和” “)’。不包括 $<$ 条件 $>$ 和的产生规则。

上下文无关语言的语法（例如 $\operatorname{LL}(1), \operatorname{LL}(k), \operatorname{LR}(1), \operatorname{LR}(k)）$ 语法表示为BNF 表示法）可以由解析器翻译成解析表。然后可以使用解析表来确定特定程序在其语法方面是否有效。
例 12.1（上下文无关文法）
考虑的例子是括号匹配，其中有两个终结符号和一个非终结符号

数学代写| DISCRETE MATHEMATICS代考请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Cryptosystem
A system that describes how to encrypt or decrypt messages
Plaintext
Message in its original form
Ciphertext
Message in its encrypted form
Cryptographer
Invents encryption algorithms
Cryptanalyst
Breaks encryption algorithms or implementations

编码理论代写

编码理论（英语：Coding theory）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、纠错，最近也用于网络编码中。不同学科（如信息论、电机工程学、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。

编码共分四类：^[1]