时间戳

首页 > 解决方案 > 如何使用自动机概念理论制作计算机语言？

programming-languages - 如何使用自动机概念理论制作计算机语言？

问题描述

我非常努力地在谷歌引擎上找到这个问题的答案。

但是我想知道这些高级编程语言是如何根据自动机原理创建的，或者自动机理论不包括在定义语言中吗？

标签： programming-languagesautomata-theory

解决方案

语言设计往往有两个重要的层次：

  1. 词法分析- 令牌外观的定义。什么是字符串文字，什么是数字，什么是变量、函数等的有效名称。
  2. 句法分析- 令牌如何协同工作以做出有意义的陈述的定义。您可以为文字赋值吗，块是什么样的，if语句是什么样的，等等。

词法分析使用正则语言完成，通常使用正则表达式定义标记。并不是说使用了 DFA（实际上大多数正则表达式实现都不是 DFA），而是正则表达式倾向于与大多数语言认为的标记很好地对齐。例如，如果您想要一种所有变量名都必须是回文的语言，那么您的语言的标记规范就必须是上下文无关的。

词法分析阶段的输入是源代码的原始字符。因此，字母表将是 ASCII 或 Unicode 或您的编译器期望的任何输入。输出是带有元数据的令牌流，例如string-literal (value: hello world)可能"hello world"在源代码中表示的。

句法分析通常使用称为LL或LR解析器的上下文无关语言的子集来完成。这是因为 CFG (PDA) 的实现是不确定的。LL 和 LR 解析是就如何解析给定表达式做出确定性决策的方法。

我们将 CFG 用于代码，因为这是发生嵌套的 Chomsky 层次结构中的级别（您可以在其中表达“深度”的概念，例如使用ifwithin an if）。层次结构的更高或更低级别是可能的，但常规语法无法轻松表达嵌套，并且上下文相关的语法可能会导致混淆（但并非闻所未闻）。

句法分析步骤的输入是令牌流，输出是某种形式的可执行结构，通常是立即执行（如在解释语言中）或存储以供以后优化和/或执行（如在编译中）的分析树语言）或其他东西（如Java等中间编译语言）。因此，CFG 的字母表是词法分析步骤指定的可能标记。

所以这整件事是一种冗长的说法，说重要的不是自动机理论，而是形式语言。我们通常希望拥有满足我们需求的最简单的语言类。这通常意味着常规标记和上下文无关语法，但并非总是如此。

正则表达式的实现不必是自动机，CFG 的实现也不能是 PDA，因为 PDA 是非确定性的，所以我们在 CFG 类的合理子集上定义确定性解析器。

推荐阅读