确定性下推自动机

DPDA 的每一步都由当前有限状态、下一输入符号和栈顶唯一决定，因此可以直接作为无回溯解析器运行。限制 ε 转移冲突很关键：即使每张转移表单独看像函数，只要机器可选择先做 ε 动作还是先读字符，仍然存在非确定性。确定性牺牲一部分语言表达力，换来唯一运行、补集闭包和更可预测的在线处理。输入结束标记常用于让机器知道“现在可以作最终决定”，否则前缀关系会干扰空栈式接受。

语言 $\{a^n{b}^n:n\ge 0\}$ 可由 DPDA 识别：读 a 唯一压栈，看到第一个 b 唯一切换到弹栈阶段，此后禁止再读 a。为看清终止条件，可在输入末尾附加不属于原字母表的标记 $⊣$：aabb 实际读作 aabb 后接 $⊣$。栈从 $Z_0$ 依次变成 $A{Z}_0,AA{Z}_0,A{Z}_0,Z_0$；只有在栈为 $Z_0$ 时读到 $⊣$ 才进入终态。空字直接读取 $⊣$ 后接受。各步由输入符号决定，没有“现在结束还是继续读”的选择。标记是输入协议的一部分，不能暗中当作普通 PDA 自动拥有的读入能力。

带不同类型括号的正确嵌套也可确定识别，因为每个右括号应匹配哪个左括号由栈顶唯一给出。

偶数长度回文语言 $\{w{w}^R:w\in \{0,1{\}}^{\ast }\}$ 是上下文无关而非确定性上下文无关的。常见的 NPDA 必须猜测何时从压栈切换到弹栈，这解释了困难，但不能单凭这台机器需要猜测就证明所有 DPDA 都失败；严格的语言类分离还需要独立证明。加入分隔符的 $\{w\mathrm{\#}{w}^R\}$ 则可确定识别：对 01#10，先把 0,1 依次压栈，读到 # 后固定切换阶段，再用 1,0 依次弹栈。

接受约定也有实质影响。在无结束标记、空栈后不能再转移的模型中，DPDA 空栈接受的语言必须无真前缀关系：若已接受 $u$，同一唯一运行在更长输入 $uv$ 上也会于读完 $u$ 时空栈，便无法读取非空 $v$。因此 $\{a^n{b}^n:n\ge 0\}$ 包含 $\epsilon$ 和非空字，不能在这种约定下直接改为空栈接受。

DPDA 是确定性解析的自动机基础。NULLABLE、FIRST与FOLLOW理路文法的 Nullable、FIRST 与 FOLLOWNullable FIRST and FOLLOW · First and follow sets以最小不动点计算文法的可空性、可能首符号及后继符号，供预测与归约表使用。分别计算可空性、开头终结符和非终结符之后可能出现的符号，为LL(1)理路LL(1) 预测分析LL(1) parsing · Predictive parsing以一个向前看token和无冲突预测表执行最左推导的确定解析算法。提供预测信息；LL(1)用一个向前看token选择最左展开。

LR项目与状态栈理路LR(0) 项目自动机与移进归约LR(0) parsing · LR(0) item automaton用项目自动机总结可行前缀，并以状态栈执行不依赖向前看的移进归约。则在右部出现后归约；SLR理路SLR 分析表SLR parsing · Simple LR parsing保留LR(0)状态，只在左部FOLLOW集合上允许归约的确定解析方法。用全局FOLLOW限制归约，LR(1)理路规范 LR(1) 分析Canonical LR(1) parsing在项目中保存局部右上下文，以一个向前看token区分归约的LR构表方法。进一步保存局部右上下文。这些构造展示了实际文法怎样得到解析器。DPDA 与一般 PDA理路下推自动机Pushdown automaton · PDA带无界栈存储的有限控制自动机。的差距说明“文法是上下文无关的”不保证存在无回溯确定解析器。

确定性上下文无关语言具有补集闭包等良好性质，但构造补自动机前要处理未读完输入就卡住及无限 $\epsilon$ 运行；简单互换终态与非终态并不足够。每个 DCFL 都有无歧义文法；歧义理路文法歧义Grammar ambiguity同一终端字有不同语法树的性质；通过完整推导区分展开次序、消歧改写、固有歧义与解析器冲突。与确定解析之间因此存在紧密联系。

不过 DCFL 对并与交一般都不封闭；只能与正则语言求交后仍保证留在 DCFL。不能把 DFA 的全部布尔闭包性质直接搬到 DPDA。