确定性上下文无关语法与上下文无关语法？

Question

我正在阅读比较语言课的笔记，我有点困惑......

上下文无关语法和确定性上下文无关语法有什么区别？我专门阅读了有关 CFG 的解析器是 O(n^3) 以及 DCFG 的编译器是 O(n) 的内容，并且并不真正理解时间复杂度的差异为何如此之大（更不用说我仍然对 CFG 成为 DCFG 的特征感到困惑）。

提前非常感谢！

Answer 1

从概念上讲，它们非常容易理解。上下文无关文法是那些可以用 BNF 表达的文法。 DCFG 是可以为其编写可用解析器的子集。

在编写编译器时，我们只对 DCFG 感兴趣。原因是“确定性”大致意味着解析中任何点要应用的下一个规则由到目前为止的输入和有限量的前瞻确定。 Knuth 在 20 世纪 60 年代发明了 LR() 编译器，并证明它可以处理任何 DCFG。从那时起，一些改进，特别是 LALR(1) 和 LL(1)，定义了可以在有限内存中解析的语法，以及我们可以编写它们的技术。

如果我们知道 BNF 是其中一种语法，我们还拥有从 BNF 自动派生解析器的技术。 Yacc、Bison 和 ANTLR 都是熟悉的例子。

我从未见过 NDCFG 的解析器，但在解析中的任何一点，它都可能需要考虑整个输入字符串以及可以应用的每个可能的解析。不难看出为什么它会变得相当大且缓慢。

---

我应该指出，许多真实的语言都是不完美的，因为它们并不完全与上下文无关，不是明确的，或者在其他方面背离了理想的 DCFG。 C/C++ 是一个很好的例子，但还有很多其他例子。这些语言通常由特殊目的规则处理，例如语义或句法谓词、特殊情况回溯或其他对性能没有影响的“技巧”。

---

评论指出某些类型的 NDCFG 很常见，并且许多工具提供了处理它们的方法。一个常见的问题是含糊不清。通过引入简单的局部语义规则来解析歧义语法相对容易，但是当然这只能生成可能的解析树之一。 NDCFG 的通用解析器可能会生成所有解析树，并且可能允许在某些任意条件下过滤这些树。这些我都不知道。

左递归不是NDCFG的特性。它对 LL() 解析器的设计提出了特殊的挑战，但对 LR() 解析器来说没有问题。

Answer 2

@inject AppState AppState
@inject JobStatsService JobStatsService

...

@code {
    private List<JobStat> jobStats;
    private int currentPage = 1;
    private int totalPages;
    private bool isLoading = true;
    private const int pageSize = 10; // Define your page size

    protected override void OnInitialized()
    {
        AppState.OnChange += StateHasChanged;
        LoadData(); // Initial load
    }

    private async void LoadData()
    {
        if (!string.IsNullOrWhiteSpace(AppState.SelectedEnvironment) &&
            !string.IsNullOrWhiteSpace(AppState.SelectedRegion))
        {
            isLoading = true;
            try
            {
                var result = await JobStatsService.GetJobStatsAsync(AppState.SelectedEnvironment, AppState.SelectedRegion, currentPage, pageSize);
                jobStats = result.Data;
                totalPages = (int)Math.Ceiling((double)result.TotalCount / pageSize);
            }
            catch (Exception ex)
            {
                Console.Error.WriteLine($"An error occurred when loading job stats: {ex.Message}");
                // Handle exceptions here, e.g., by showing an error message to the user
            }
            finally
            {
                isLoading = false;
                StateHasChanged(); // Re-render the component with the new data
            }
        }
    }

    // Make sure to unsubscribe from the AppState event when the component is disposed
    public void Dispose()
    {
        AppState.OnChange -= StateHasChanged;
    }

    // Add your pagination methods here
    private async Task GoToPage(int newPageNumber)
    {
        if (newPageNumber < 1 || newPageNumber > totalPages)
        {
            return; // Page number is out of bounds
        }

        currentPage = newPageNumber;
        await LoadData();
    }

    // Example of methods for handling pagination button clicks
    private Task PreviousPage() => GoToPage(currentPage - 1);
    private Task NextPage() => GoToPage(currentPage + 1);
}