搜索

[24464] 2015-11-14_第一个C语言编译器是怎样编写的？

文档创建者：s7ckTeam
浏览次数：3
最后更新：2025-01-18
2015-11-14_第一个C语言编译器是怎样编写的？ 第 一 个   C   语 言 编 译 器 是 怎 样 编 写 的 ？ C h a o b s   L i n u x 中 国   2 0 1 5 - 1 1 - 1 4 首 先 向 C 语 言 之 父 D e n n i s   R i t c h i e 致 敬 ！ 当 今 几 乎 所 有 的 实 用 的 编 译 器 / 解 释 器 （ 以 下 统 称 编 译 器 ） 都 是 用 C 语 言 编 写 的 ， 有 一 些 语 言 比 如 C l o j u r e , J y t h o n 等 是 基 于 J V M 或 者 说 是 用 J a v a 实 现 的 ， I r o n P y t h o n 等 是 基 于 . N E T 实 现 的 ， 但 是 J a v a 和 C # 等 本 身 也 要 依 靠 C / C + + 来 实 现 ， 等 于 是 间 接 调 用 了 C 。 所 以 衡 量 某 种 高 级 语 言 的 可 移 植 性 其 实 就 是 在 讨 论 A N S I / I S O   C 的 移 植 性 。 C 语 言 是 很 低 级 的 语 言 ， 很 多 方 面 都 近 似 于 汇 编 语 言 ， 在 《 I n t e l   3 2 位 汇 编 语 言 程 序 设 计 》 一 书 中 ， 甚 至 介 绍 了 手 工 把 简 单 的 C 语 言 翻 译 成 汇 编 的 方 法 。 对 于 编 译 器 这 种 系 统 软 件 ， 用 C 语 言 来 编 写 是 很 自 然 不 过 的 ， 即 使 是 像 P y t h o n 这 样 的 高 级 语 言 依 然 在 底 层 依 赖 于 C 语 言 （ 举 P y t h o n 的 例 子 是 因 为 I n t e l 的 黑 客 正 在 尝 试 让 P y t h o n 不 需 要 操 作 系 统 就 能 运 行 — — 实 际 上 是 免 去 了 B I O S 上 的 一 次 性 C 代 码 ） 。 现 在 的 学 生 ， 学 过 编 译 原 理 后 ， 只 要 有 点 编 程 能 力 的 都 可 以 实 现 一 个 功 能 简 单 的 类 C 语 言 编 译 器 。 可 是 问 题 来 了 ， 不 知 道 你 有 没 有 想 过 ， 大 家 都 用 C 语 言 或 基 于 C 语 言 的 语 言 来 写 编 译 器 ， 那 么 世 界 上 第 一 个 C 语 言 编 译 器 又 是 怎 么 编 写 的 呢 ？ 这 不 是 一 个 “ 鸡 和 蛋 ” 的 问 题 … … 还 是 让 我 们 回 顾 一 下 C 语 言 历 史 ： 1 9 7 0 年 T o m p h s o n 和 R i t c h i e 在 B C P L （ 一 种 解 释 型 语 言 ） 的 基 础 上 开 发 了 B 语 言 ， 1 9 7 3 年 又 在 B 语 言 的 基 础 上 成 功 开 发 出 了 现 在 的 C 语 言 。 在 C 语 言 被 用 作 系 统 编 程 语 言 之 前 ， T o m p h s o n 也 用 过 B 语 言 编 写 过 操 作 系 统 。 可 见 在 C 语 言 实 现 以 前 ， B 语 言 已 经 可 以 投 入 实 用 了 。 因 此 第 一 个 C 语 言 编 译 器 的 原 型 完 全 可 能 是 用 B 语 言 或 者 混 合 B 语 言 与 P D P 汇 编 语 言 编 写 的 。 我 们 现 在 都 知 道 ， B 语 言 的 执 行 效 率 比 较 低 ， 但 是 如 果 全 部 用 汇 编 语 言 来 编 写 ， 不 仅 开 发 周 期 长 、 维 护 难 度 大 ， 更 可 怕 的 是 失 去 了 高 级 程 序 设 计 语 言 必 需 的 移 植 性 。 所 以 早 期 的 C 语 言 编 译 器 就 采 取 了 一 个 取 巧 的 办 法 ： 先 用 汇 编 语 言 编 写 一 个 先 用 汇 编 语 言 编 写 一 个 C 语 言 的 一 个 子 集 的 编 译 器 ， 再 通 过 这 个 子 集 去 递 推 完 成 完 整 语 言 的 一 个 子 集 的 编 译 器 ， 再 通 过 这 个 子 集 去 递 推 完 成 完 整 的 的 C 语 言 编 译 器 。 语 言 编 译 器 。 详 细 的 过 程 如 下 ： 先 创 造 一 个 只 有 C 语 言 最 基 本 功 能 的 子 集 ， 记 作 C 0 语 言 ， C 0 语 言 已 经 足 够 简 单 了 ， 可 以 直 接 用 汇 编 语 言 编 写 出 C 0 的 编 译 器 。 依 靠 C 0 已 有 的 功 能 ， 设 计 比 C 0 复 杂 ， 但 仍 然 不 完 整 的 C 语 言 的 又 一 个 子 集 C 1 语 言 ， 其 中 C 0 属 于 C 1 ， C 1 属 于 C ， 用 C 0 开 发 出 C 1 语 言 的 编 译 器 。 在 C 1 的 基 础 上 设 计 C 语 言 的 又 一 个 子 集 C 2 语 言 ， C 2 语 言 比 C 1 复 杂 ， 但 是 仍 然 不 是 完 整 的 C 语 言 ， 开 发 出 C 2 语 言 的 编 译 器 … … 如 此 直 到 C N ， C N 已 经 足 够 强 大 了 ， 这 时 候 就 足 够 开 发 出 完 整 的 C 语 言 编 译 器 的 实 现 了 。 至 于 这 里 的 N 是 多 少 ， 这 取 决 于 你 的 目 标 语 言 （ 这 里 是 C 语 言 ） 的 复 杂 程 度 和 程
序 员 的 编 程 能 力 — — 简 单 地 说 ， 如 果 到 了 某 个 子 集 阶 段 ， 可 以 很 方 便 地 利 用 现 有 功 能 实 现 C 语 言 时 ， 那 么 你 就 找 到 N 了 。 下 面 的 图 说 明 了 这 个 抽 象 过 程 ： C 语 言 C N 语 言 … … C 0 语 言 汇 编 语 言 机 器 语 言 那 么 这 种 大 胆 的 子 集 简 化 的 方 法 ， 是 怎 么 实 现 的 ， 又 有 什 么 理 论 依 据 呢 ？ 先 介 绍 一 个 概 念 ， S e l f - C o m p i l e “ 自 编 译 ” ， 也 就 是 对 于 某 些 具 有 明 显 自 举 性 质 的 强 类 型 （ 所 谓 强 类 型 就 是 程 序 中 的 每 个 变 量 必 须 声 明 类 型 后 才 能 使 用 ， 比 如 C 语 言 ， 相 反 有 些 脚 本 语 言 则 根 本 没 有 类 型 这 一 说 法 ） 编 程 语 言 ， 可 以 借 助 它 们 的 一 个 有 限 小 子 集 ， 通 过 有 限 次 数 的 递 推 来 实 现 对 它 们 自 身 的 表 述 ， 这 样 的 语 言 有 C 、 P a s c a l 、 A d a 等 等 ， 至 于 为 什 么 可 以 自 编 译 ， 可 以 参 见 清 华 大 学 出 版 社 的 《 编 译 原 理 》 ， 书 中 实 现 了 一 个 P a s c a l 的 子 集 的 编 译 器 。 总 之 ， 已 经 有 计 算 机 科 学 家 证 明 了 ， C 语 言 理 论 上 是 可 以 通 过 上 面 说 的 C V M 的 方 法 实 现 完 整 的 编 译 器 的 ， 那 么 实 际 上 是 怎 样 做 到 简 化 的 呢 ？ 这 张 图 是 不 是 有 点 熟 悉 ？ 对 了 就 是 在 讲 虚 拟 机 的 时 候 见 到 过 ， 不 过 这 里 是 C V M （ C   L a n g u a g e   V i r t u a l   M a c h i n e ） ， 每 种 语 言 都 是 在 每 个 虚 拟 层 上 可 以 独 立 实 现 编 译 的 ， 并 且 除 了 C 语 言 外 ， 每 一 层 的 输 出 都 将 作 为 下 一 层 的 输 入 （ 最 后 一 层 的 输 出 就 是 应 用 程 序 了 ） ， 这 和 滚 雪 球 是 一 个 道 理 。 用 手 （ 汇 编 语 言 ） 把 一 小 把 雪 结 合 在 一 起 ， 一 点 点 地 滚 下 去 就 形 成 了 一 个 大 雪 球 ， 这 大 概 就 是 所 谓 的 0 生 生 1 ， ， 1 生 生 C ， ， C 生 万 物 生 万 物 吧 ？ 下 面 是 C 9 9 的 关 键 字 ： 仔 细 看 看 ， 其 实 其 中 有 很 多 关 键 字 是 为 了 帮 助 编 译 器 进 行 优 化 的 ， 还 有 一 些 是 用 来 限 定 变 量 、 函 数 的 作 用 域 、 链 接 性 或 者 生 存 周 期 （ 函 数 没 有 ） 的 ， 这 些 在 编 译 器 实 现 的 早 期 根 本 不 必 加 上 ， 于 是 可 以 去 掉 a u t o ,   r e s t r i c t ,   e x t e r n ,   v o l a t i l e ,   c o n s t ,   s i z e o f ,   s t a t i c ,   i n l i n e ,   r e g i s t e r ,   t y p e d e f ， 这 样 就 形 成 了 C 的 子 集 ， C 3 语 言 ， C 3 语 言 的 关 键 字 如 下 ： 1 .   a u t o                 e n u m                 r e s t r i c t                 u n s i g n e d 2 .   b r e a k               e x t e r n             r e t u r n                     v o i d 3 .   c a s e                 f l o a t               s h o r t                       v o l a t i l e 4 .   c h a r                 f o r                   s i g n e d                     w h i l e 5 .   c o n s t               g o t o                 s i z e o f                     _ B o o l 6 .   c o n t i n u e         i f                     s t a t i c                     _ C o m p l e x 7 .   d e f a u l t           i n l i n e             s t r u c t                     _ I m a g i n a r y 8 .   d o                     i n t                   s w i t c h               9 .   d o u b l e             l o n g                 t y p e d e f 1 0 .   e l s e                 r e g i s t e r         u n i o n 1 1 .   / / 共 3 7 个 1 .   e n u m               u n s i g n e d
再 想 一 想 ， 发 现 C 3 中 其 实 有 很 多 类 型 和 类 型 修 饰 符 是 没 有 必 要 一 次 性 都 加 上 去 的 ， 比 如 三 种 整 型 ， 只 要 实 现 i n t 就 行 了 ， 因 此 进 一 步 去 掉 这 些 关 键 词 ， 它 们 是 ： u n s i g n e d ,   f l o a t ,   s h o r t ,   c h a r ( c h a r   是   i n t ) ,   s i g n e d ,   _ B o o l ,   _ C o m p l e x ,   _ I m a g i n a r y ,   l o n g ， 这 样 就 形 成 了 我 们 的 C 2 语 言 ， C 2 语 言 关 键 字 如 下 ： 继 续 思 考 ， 即 使 是 只 有 1 8 个 关 键 字 的 C 2 语 言 ， 依 然 有 很 多 高 级 的 地 方 ， 比 如 基 于 基 本 数 据 类 型 的 复 合 数 据 结 构 ， 另 外 我 们 的 关 键 字 表 中 是 没 有 写 运 算 符 的 ， 在 C 语 言 中 的 复 合 赋 值 运 算 符 - > 、 运 算 符 的 + + 、 –   等 过 于 灵 活 的 表 达 方 式 此 时 也 可 以 完 全 删 除 掉 ， 因 此 可 以 去 掉 的 关 键 字 有 ： e n u m ,   s t r u c t ,   u n i o n ， 这 样 我 们 可 以 得 到 C 1 语 言 的 关 键 字 ： 2 .   b r e a k               r e t u r n             v o i d 3 .   c a s e                 f l o a t               s h o r t     4 .   c h a r                 f o r                   s i g n e d           w h i l e 5 .   g o t o                 _ B o o l 6 .   c o n t i n u e         i f                     _ C o m p l e x 7 .   d e f a u l t           s t r u c t             _ I m a g i n a r y 8 .   d o                     i n t                   s w i t c h               9 .   d o u b l e             l o n g       1 0 .   e l s e                 u n i o n 1 1 .   / / 共 2 7 个 1 .   e n u m 2 .   b r e a k             r e t u r n             v o i d 3 .   c a s e 4 .   f o r                   w h i l e 5 .   g o t o               6 .   c o n t i n u e         i f                 7 .   d e f a u l t           s t r u c t       8 .   d o                     i n t                   s w i t c h               9 .   d o u b l e   1 0 .   e l s e                 u n i o n 1 1 .   / / 共 1 8 个 1 .   b r e a k             r e t u r n             v o i d 2 .   c a s e 3 .   f o r                   w h i l e
来 源 ： 伯 乐 在 线 原 文 ： h t t p : / / b l o g . j o b b o l e . c o m / 9 4 3 1 1 / 作 者 ：   C h a o b s 接 近 完 美 了 ， 不 过 最 后 一 步 手 笔 自 然 要 大 一 点 。 这 个 时 候 数 组 和 指 针 也 要 去 掉 了 ， 另 外 C 1 语 言 其 实 仍 然 有 很 大 的 冗 杂 度 ， 比 如 控 制 循 环 和 分 支 的 都 有 多 种 表 述 方 法 ， 其 实 都 可 简 化 成 一 种 ， 具 体 的 来 说 ， 循 环 语 句 有 w h i l e 循 环 ， d o … w h i l e 循 环 和 f o r 循 环 ， 只 需 要 保 留 w h i l e 循 环 就 够 了 ； 分 支 语 句 又 有 i f … { } ,   i f … { } … e l s e ,   i f … { } … e l s e   i f … ,   s w i t c h ， 这 四 种 形 式 ， 它 们 都 可 以 通 过 两 个 以 上 的 i f … { } 来 实 现 ， 因 此 只 需 要 保 留 i f , … { } 就 够 了 。 可 是 再 一 想 ， 所 谓 的 分 支 和 循 环 不 过 是 条 件 跳 转 语 句 罢 了 ， 函 数 调 用 语 句 也 不 过 是 一 个 压 栈 和 跳 转 语 句 罢 了 ， 因 此 只 需 要 g o t o （ 未 限 制 的 g o t o ） 。 因 此 大 胆 去 掉 所 有 结 构 化 关 键 字 ， 连 函 数 也 没 有 ， 得 到 的 C 0 语 言 关 键 字 如 下 ： 这 已 经 是 简 约 的 极 致 了 。 只 有 5 个 关 键 字 ， 已 经 完 全 可 以 用 汇 编 语 言 快 速 的 实 现 了 。 通 过 逆 向 分 析 我 们 还 原 了 第 一 个 C 语 言 编 译 器 的 编 写 过 程 ， 也 感 受 到 了 前 辈 科 学 家 们 的 智 慧 和 勤 劳 ！ 我 们 都 不 过 是 巨 人 肩 膀 上 的 灰 尘 罢 了 ！ 0 生 1 ， 1 生 C ， C 生 万 物 ， 实 在 巧 妙 ！ 3 .   f o r                   w h i l e 4 .   g o t o               5 .   c o n t i n u e         i f                 6 .   d e f a u l t   7 .   d o                     i n t                   s w i t c h               8 .   d o u b l e   9 .   e l s e 1 0 .   / / 共 1 5 个 1 .   b r e a k         v o i d 2 .   g o t o               3 .   i n t         4 .   d o u b l e   5 .   / / 共 5 个
阅 读 原 文
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理