Подскажите как правильно написать регулярное выражение

Точно без закрывающего тега "a" идет?

<li><a href="http://site.com/link1">Link1</li>

simple html dom parser

будет проще для вас

$data = array();
preg_match_all('#<li class="menu">.+?</div>\s*</li>#s', $str, $out);
foreach($out[0] as $v){
	preg_match('#<li class="menu">\s*<a href="(.+?)".*?>(.*?)</a>#s', $v, $m);
	$data['cat'] = $m[2];
	$data['url'] = $m[1];
	$data['links'] = array();
	
	preg_match_all('#<li><a href="(.*?)".*?>(.*?)</a>#s', $v, $m);
	for($i=0; $i<count($m[0]); $i++){
		$data['links'][] = array($m[1][$i], $m[2][$i]);
	}
}

print_r($data);

Хотя согласен, для вас проще будет парсить на html парсере. А лучше учите xpath запросы.

Если вы еще не нашли ответа или вам понадобилась новая регулярка, то вот вам инструмент http://regex101.com/

Ну очень хорошая штука для проверки всяких регулярок с генератором кода для питона, пхп и js