Archive for the ‘code’ tag

Generating Random Sentences from a Context Free Grammar using VisualBasic for Excel

without comments

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.

Written by Jared

August 24th, 2010 at 10:08 am

Posted in Uncategorized

Tagged with ,