知识卡片

问题卡 · 5654.d.1.a.3.d.12 · 生成模型:未记录

分词成本须计入词素长度

理解等级:中级

即使假设next_token常数时间,本例lex也先strlen求词素长度,再逐字符isdigit分类,随后插入哈希表。长度L的扫描本身就有O(L)工作;表内查找还受散列、比较和链长影响,不能仅因插入常见期望O(1)就称整个lex无条件常数时间。

控制流也区分几种业务结果:没有词素时释放刚分配的Symbol并返回lexit;分配或插入失败返回error;已存在时不保留新Symbol;成功处理后返回token分类。返回digit/other描述本次词素类型,不表示所有后续语法或语义处理都成功。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      next_token的运行时间为常量级时,lex的时间复杂度为O(1)。因为,lex只是简单地调用复杂度为O(1)的函数chtbl_insert。 示例8-4:词法分析器的头文件 示例8-5:词法分析器的实现

    参考来源

    - 位置:《算法精解:C语言描述》第8章《链式哈希表的例子:符号表》(spine1275;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1242.html;u131-ch08-013)。 - 结论依据:131最后复杂度段、02819–02820 strlen、完整for循环、chtbl_insert状态分支和return token全部已读;未测试输入或给未知next_token的复杂度。 - 原始内容:next_token的运行时间为常量级时,lex的时间复杂度为O(1)。因为,lex只是简单地调用复杂度为O(1)的函数chtbl_insert。 示例8-4:词法分析器的头文件 示例8-5:词法分析器的实现