C语言中的上下文无关文法 [英] Context-free grammar in C

问题描述

我分配了一个程序，用C编写一个程序，该程序使用以下上下文无关文法显示一些（n <50）有效的上下文无关文法字符串：

I have an assignment to make a program in C that displays a number (n < 50) of valid, context-free grammar strings using the following context-free grammar:

S -> AA|0
A -> SS|1

我对如何做到这一点了解很少，但是在对它们进行了越来越多的分析之后

I had few concepts of how to do it, but after analyzing them more and more, none of them were right.

现在，我打算制作一个数组并随机更改 [...，A，.. 。] 表示 [...，S，S，...] 或 [...，1， ...] 直到只有0和1，然后检查是否已经随机生成了同一个东西。

For now, I'm planning to make an array and randomly change [..., A, ...] for [..., S, S, ...] or [..., 1, ...] until there are only 0s and 1s and then check whether the same thing was already randomly generated.

我仍然没有我坚信这是正确的方法，但我仍然不确切知道该怎么做或在哪里保留最终用语，因为基本形式将是不同长度的字符数组。而且，在C语言中，一个二维的char数组等于一个字符串数组吗？

I'm still not convinced if that is the right approach, and I still don't know exactly how to do that or where to keep the final words because the basic form will be an array of chars of different length. Also, in C, is a two dimensional array of chars equal to an array of strings?

这有意义吗，这是一种正确的方法吗？还是我遗漏了什么？

Does this make any sense, and is it a proper way to do it? Or am I missing something?

推荐答案

您每次需要决定某件事时都可以简单地做出随机决定。例如：

You can simply make a random decision every time you need to decide on something. For example:

function A():
  if (50% random chance)
    return "1"
  else
    return concat(S(), S())

function S():
  if (50% random chance)
    return "0"
  else
    return concat(A(), A())

多次调用 S（）给我这些输出：

Calling S() multiple times give me these outputs:

"0"
"00110110100100101111010111111111001111101011100100011000000110101110000110101110
 10001000110001111100011000101011000001101111000110110011101010111111111011010011
 10000000101111100100011011010000000101000111110010001000101001100110100111111111
 1001010011"
"11"
"10010010101111010111101"

语法的所有有效字符串。请注意，您可能需要调整一些随机机会。该示例很有可能生成非常小的字符串，例如 11 。

All valid strings for your grammar. Note that you may need to tweak a little the random chances. This sample has a high probability to generate very small strings like "11".

这篇关于C语言中的上下文无关文法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！