First some general advise. I personally prefer alternations instead of multiple rule definitions, if only for the fact that it makes the grammar look more BNF-ish (which is easy for me to read) Thus:

Address : '(' /address/i '=' AddressTCP ')'
Address : '(' /address/i '=' AddressIPC ')'
Address : '(' /address/i '=' AddressSPX ')'
Address : '(' /address/i '=' AddressPipe ')'
[download]

Would become:

Address: '(' /address/i '=' (AddressTCP | AddressIPC | AddressSPX | Ad
+dressPipe ) ')'
[download]

Or better yet:

Address: '(' /address/i '=' AddressProtocol ')'
AddressProtocol: AddressTCP  |
                            AddressIPC   |
                            AddressSPX  |
                            AddressPipe
[download]

Also:

TNSEntry : NetServiceName '=' Description
TNSEntry : NetServiceName '=' DescriptionList
[download]

Would become:

TNSEntry: NetServiceName '=' (Description | DescriptionList)
[download]

Note: In this last example order can matter in some situtations, you'll just have to play with it.

Now as far as:
The second problem is tied to the order of the clauses to be matched. If I take the following line:
AddressTCP : Community(?) ProtocolTCP Host Port
It will match the code only if they come in that exact order. There are no rules stating that Community needs to be first and Protocol needs to be second ... The obvious solution is to create create every permutation of this line. My question is "Is there an easier way?" What could be a relatively small program could otherwise become quite unwieldly.

I guess I don't understand what you are talking about here. The rule that you have states: AddressTCP by definition is: An optional Community followed by required Protocol, Host, and Port. So yes order does matter here. The rule does require that if a community appears, it must come before the protocol. I don't know enough about the TNSNAMES.ORA file to divine the intended meaning. A clearer description of the exact syntax of this line may help.

Also are you parsing each line individually just so you can report which lines contain errors? If so you can accomplish the same thing by letting Parse::RecDescent parse the entire input for you. There's no need to parse the document before you "parse" the document. Anyway that's just my $.02 I could be wrong.