Archive for the ‘code’ tag
Generating Random Sentences from a Context Free Grammar using VisualBasic for Excel
According to Google, generating random sentences from a CFG is a common computer science homework problem, which means there are no solutions online. Here is a solution in VisualBasic for Applications (VBA):
Function GenerateSentence(productor As String) As String
Dim rule As Range
' Get list of rules for productor:
Dim rules As Collection
Set rules = New Collection
With Sheet1.Range("A1:A99")
Set rule = .Find(productor, LookAt:=xlWhole) ' Match whole cell
Do
rules.Add (rule.Address)
Set rule = .FindNext(rule)
Loop While rule.Address <> rules(1) ' Until FindNext loops around
End With
' Choose a random item from rules (VBA must do by reference):
Set rule = Sheet1.Range(CStr(rules.Item(Int(rules.Count * Rnd() + 1))))
' Evaluate right-hand side of rule:
Dim production As String
Dim i As Integer ' i = 0
Do
i = i + 1
production = rule.Offset(0, i).Value
If left(production, 1) = Chr(34) Then ' Chr(34) = Double quote
' Evaluate terminal by stripping quotes:
GenerateSentence = GenerateSentence & Mid(production, 2, Len(production) - 2)
ElseIf Len(production) <> 0 Then
' Evaluate non-terminal recursively:
GenerateSentence = GenerateSentence & GenerateSentence(production)
End If
Loop While Len(production) > 0 ' Until empty column
End Function
Error handling is left as an exercise for the reader.
Input
Sheet1 contains one production rule per row. Column A is the left-hand side of the production rule and each cell to the right contains a terminal enclosed in double-quotes or a non-terminal that matches other cells in column A. For Example 5 in Wikipedia’s article on CFGs, Sheet1 would look like:
| A | B | C | D | |
|---|---|---|---|---|
| 1 | S | "x" | ||
| 2 | S | "y" | ||
| 3 | S | "z" | ||
| 4 | S | S | " + " | S |
| 5 | S | S | " – " | S |
| 6 | S | S | " * " | S |
| 7 | S | S | " / " | S |
| 8 | S | "(" | S | ")" |
Environment
Create a macro that initializes the random number generator (Randomize) and then calls GenerateSentence with the start symbol as input. GenerateSentence returns a string that can be put in the Value of a cell.


