C程序源代碼可以根據C語法進行解析（在CFG中描述）並最終轉化爲許多AST。我正在考慮是否存在這樣的工具：它可以做相反的事情，首先根據CFG隨機生成許多AST，其中包括沒有具體字符串值的標記，只是標記的類型，然後生成具體根據正則表達式中令牌的定義來定義令牌。任何工具都可以根據語言語法隨機生成源代碼？
我可以想象，第一步看起來像一個迭代非終端替換，它是隨機的，可以被一定數量的迭代次數限制。第二步是根據正則表達式隨機生成字符串。
有什麼工具可以做到這一點嗎？
「數據生成語言」DGL這樣做，增加了對正在輸出的語法中生成概率加權的能力。
通常，遞歸下降解析器可以很直接地重寫成一組遞歸過程來生成而不是解析/識別語言。
給定語言的上下文無關語法，有可能generate a random string that matches the grammar。
例如，nearley解析器生成器包括an implementation of an "unparser"可以從一個語法生成字符串。
在Prolog中使用確定子句語法可以完成相同的任務。使用定語從句語法的句子生成器的例子被給出here。
如果你有語法的規範化形式的模型（所有類似的規則）：
LHS = RHS1 RHS2 ... RHSn ;
和語言prettyprinter（例如，AST文本轉換工具），你可以建立這些漂亮的一個容易。
只需將目標符號作爲單位樹開始。
Repeat until no nonterminals are left:
Pick a nonterminal N in the tree;
Expand by adding children for the right hand side of any rule
whose left-hand side matches the nonterminal N
對於攜帶值（例如，變量名，數字，字符串，...）的終端，您必須生成隨機內容。
上述算法的複雜性在於它沒有明確的終止。你真正想要做的是挑選一些樹的大小限制，然後運行算法，直到所有的非終結者不見了或者你超出了限制。在後一種情況下，回溯，取消最後的替換，並嘗試其他的東西。這讓你有一個深度優先的搜索你的確定大小的AST。
然後相當結果。其prettyprinter part這是很難得到正確的。
[你可以自己構建所有這些東西，包括美麗的打印機，但這是相當多的工作。我使用語言參數化的方式直接構建包含所有這些機器的工具;看到我的生物]。
即使形成良好的AST，一個令人討厭的問題是它們可能是無意義的;您可能會生成一個整數X的聲明，併爲其指定一個字符串文字值，但對於不允許的語言。你或許可以消除一些簡單的問題，但語言語義可能非常複雜，以C++爲例。確保你最終得到一個語義上有意義的程序是非常困難的;實質上，您必須解析生成的文本，並對其執行名稱和類型解析/檢查。對於C++，您需要一個完整的C++前端。
隨機生成的問題是，對於許多CFG，輸出字符串的預期長度是無限的（使用對應於非終端符號的生成函數和對應於規則的方程，可以容易地計算預期長度的語法）;你必須以某種方式控制製作的相對概率，以保證融合;例如，有時候，將每個生產規則加權爲與其RHS長度相反的非終端符號加權
關於此主題的更多內容如下： Noam Chomsky，Marcel-Paul Sch \「{u} tzenberger ，「語境無關語言的代數理論」，pp。\ 118-161，P. Braffort and D. Hirschberg（eds。），Computer Programming and Formal Systems，North-Holland（1963） （參見維基百科條目在Chomsky-Schützenberger枚舉定理上）
但是......爲什麼？：p我想你可以 - 如果你遵循CFG規範，你肯定會拿出至少在語法上有效的C代碼，不要以爲有人曾試圖做這樣的事情 - 你可能需要寫一些反向解析器...... – Robert 2010-12-17 05:56:46
我和幾個人一起工作......（這是個玩笑;我愛我所有的同事）。 – 2010-12-17 05:56:55
有沒有什麼理由想要隨機的，毫無意義的源代碼，這可能會（很可能）什麼都不做？ – 2010-12-17 05:57:04